QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669820#8760. 不等式MIS_T__WA 0ms3596kbC++231.4kb2024-10-23 19:46:232024-10-23 19:46:24

Judging History

你现在查看的是最新测评结果

  • [2024-10-23 19:46:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3596kb
  • [2024-10-23 19:46:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
    int n,m;
    cin >> n >> m;
    vector g(n,vector<int>(0));
    vector<int>num(n);
    for ( int i = 0 ; i < m ; i++ ) {
        int x,y,z;
        cin >> x >> y >> z;
        x--,y--,z--;
        g[x].emplace_back(y);
        g[x].emplace_back(z);
        num[y]++;
        num[z]++;
    }
    i64 ans = 0;
    vector<i64>vis(n);
    vector<i64>vis0(n);
    int f = 0;
    int cur;
    auto dfs = [&](auto& dfs, int p)->void{
        i64 res = 0;
        vis0[p] = cur;
        for ( auto q : g[p] ) {
            if ( vis0[q] == cur ) f = 1;
            if(!vis[q]) {
                dfs(dfs,q);
            }
            res += vis[q];
        }
        if ( vis[p] > 1000000000 ) f = 1;
        vis[p] = max(res,1LL);
    };
    
    for ( int i = 0 ; i < n ; i++ ) {
        if ( num[i] == 0 ) {
            cur = i+1;
            dfs(dfs,i);
        }
    }
    for ( int i = 0 ; i < n ; i++ ) {
        if ( !vis[i] ) f = 1;
        ans += vis[i];
    }
    if ( f ) {
        cout << -1 << '\n';
        return;
    }
    if ( ans > 1000000000 ) cout << -1 << '\n';
    else cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while ( T-- ) {
        solve(); 
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3596kb

input:

3 1
1 2 2

output:

-1

result:

wrong answer 1st numbers differ - expected: '4', found: '-1'