QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631308#8760. 不等式JinguluWA 3ms12852kbC++171.1kb2024-10-12 00:13:022024-10-12 00:13:03

Judging History

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

  • [2024-10-12 00:13:03]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:12852kb
  • [2024-10-12 00:13:02]
  • 提交

answer


#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=200010,mod=1e9;
vector<pair<int,int> > h[N];
int dian[N];
int idx;
int q[N];
int f[N];
int n,m;
void tp(){
    for(int i=1;i<=n;i++){
        if(dian[i]==0){
            //cout<<i<<" ";
            q[++idx]=i;
            f[i]=1;
        }
    }
    //cout<<idx;
    for(int i=1;i<=idx;i++){
        int u=q[i];
        int w=f[u];
        for(int j=0;j<h[u].size();j++){
            int fu=h[u][j].first,c=h[u][j].second;
            if(f[c]!=0){
                f[fu]=min(mod,max(f[fu],w+f[c]));
                dian[fu]--;
                if(dian[fu]==0) q[++idx]=fu;
            } 
        }
    }
}


signed main(){

    cin>>n>>m;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        h[b].push_back({a,c});
        h[c].push_back({a,b});
        dian[a]+=2;
    }

    tp();
   // cout<<idx<<" ";
    if(idx!=n){
        cout<<-1;
        return 0;
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans+=f[i];
    if(ans>1e9) cout<<-1;
    else cout<<ans;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 12136kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11524kb

input:

3 1
1 2 3

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 3ms
memory: 12604kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 11556kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 3ms
memory: 12112kb

input:

3 1
1 2 2

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 3ms
memory: 12776kb

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #7:

score: 0
Accepted
time: 3ms
memory: 12236kb

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #8:

score: 0
Accepted
time: 0ms
memory: 11972kb

input:

5 1
1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #9:

score: 0
Accepted
time: 0ms
memory: 12852kb

input:

5 1
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: -100
Wrong Answer
time: 3ms
memory: 12120kb

input:

5 2
1 2 3
2 3 4

output:

-1

result:

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