Submission #3235630
Source Code Expand
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> #include <functional> #include <utility> using namespace std; typedef long long lli; typedef pair<int,int> pii; typedef pair<lli,int> pli; int n,m; vector<pii> adj[100001]; lli l[100001],r[100001],cost[100001]; int vis[100001],depth[100001]; int f=1; lli c=-1; void dfs(int cur,int p,lli sum,int d) { vis[cur]=1; depth[cur] = d; cost[cur] = sum; for(auto &it:adj[cur]) { if(!vis[it.second]) dfs(it.second, cur, sum+(d%2==1 ? -it.first : it.first),d+1); else if(it.second != p && depth[it.second] < d) { if((d-depth[it.second])%2==1) { if(it.first != sum - cost[it.second]) f=0; } else { if(it.first+sum-cost[it.second]<=0 || (it.first + sum-cost[it.second])%2!=0) f=0; else { if(c!=-1 && (it.first+sum-cost[it.second])/2!=c) c=-2; else if(c==-1) c=(it.first+sum-cost[it.second])/2; } } } } if(d%2==0) { l[1] = max(l[1], sum+1); r[1] = min(r[1], sum+r[cur]); } else { l[1] = max(l[1], sum-r[cur]); r[1] = min(r[1], sum-1); } } int main() { scanf("%d%d",&n,&m); for(int i=0,u,v,w;i<m;i++) { scanf("%d%d%d",&u,&v,&w); adj[u].push_back(pii(w,v)); adj[v].push_back(pii(w,u)); } for(int i=1;i<=n;i++) { int mx=1e9; for(auto &it:adj[i]) mx = min(mx,it.first-1); l[i]=1; r[i]=mx; } vis[1]=1; for(auto &it:adj[1]) if(!vis[it.second]) { dfs(it.second, 1, it.first, 1); } if(!f || l[1]>r[1] || c==-2) puts("0"); else if(c==-1) printf("%lld\n",max(0ll,r[1]-l[1]+1)); else printf("%d\n",1); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - + Graph |
User | ae04071 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1643 Byte |
Status | WA |
Exec Time | 54 ms |
Memory | 16640 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:47:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&m); ^ ./Main.cpp:49:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&u,&v,&w); ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sampleNo.txt, samplePath.txt, sampleTri.txt |
All | OK_0.txt, OK_1.txt, OK_2.txt, OK_3.txt, OK_4.txt, close_0.txt, close_1.txt, close_2.txt, close_3.txt, close_4.txt, many_0.txt, many_1.txt, many_2.txt, many_3.txt, many_4.txt, many_5.txt, many_6.txt, many_7.txt, max.txt, maxBip.txt, multiple_0.txt, multiple_1.txt, multiple_2.txt, multiple_3.txt, multiple_4.txt, multiple_5.txt, multiple_6.txt, multiple_7.txt, oddLoop.txt, oddLoop_0.txt, oddLoop_1.txt, oddLoop_2.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_8.txt, rnd_9.txt, sampleNo.txt, samplePath.txt, sampleTri.txt, star.txt, star_0.txt, star_1.txt, unique_0.txt, unique_1.txt, unique_2.txt, unique_3.txt, unique_4.txt, unique_5.txt, unique_6.txt, unique_7.txt, unique_8.txt, unique_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
OK_0.txt | AC | 42 ms | 9728 KB |
OK_1.txt | AC | 42 ms | 9856 KB |
OK_2.txt | AC | 46 ms | 9856 KB |
OK_3.txt | AC | 42 ms | 9856 KB |
OK_4.txt | AC | 42 ms | 9856 KB |
close_0.txt | AC | 50 ms | 10624 KB |
close_1.txt | WA | 49 ms | 10240 KB |
close_2.txt | AC | 49 ms | 10496 KB |
close_3.txt | AC | 51 ms | 9728 KB |
close_4.txt | AC | 50 ms | 9984 KB |
many_0.txt | AC | 48 ms | 10112 KB |
many_1.txt | AC | 50 ms | 10240 KB |
many_2.txt | AC | 53 ms | 10368 KB |
many_3.txt | AC | 51 ms | 10368 KB |
many_4.txt | AC | 52 ms | 10496 KB |
many_5.txt | AC | 52 ms | 10496 KB |
many_6.txt | AC | 51 ms | 10368 KB |
many_7.txt | AC | 50 ms | 10240 KB |
max.txt | WA | 30 ms | 5632 KB |
maxBip.txt | AC | 37 ms | 7168 KB |
multiple_0.txt | WA | 48 ms | 9984 KB |
multiple_1.txt | WA | 50 ms | 10240 KB |
multiple_2.txt | WA | 51 ms | 10368 KB |
multiple_3.txt | WA | 51 ms | 10368 KB |
multiple_4.txt | WA | 52 ms | 10496 KB |
multiple_5.txt | WA | 52 ms | 10496 KB |
multiple_6.txt | WA | 51 ms | 10368 KB |
multiple_7.txt | WA | 50 ms | 10240 KB |
oddLoop.txt | AC | 54 ms | 16640 KB |
oddLoop_0.txt | AC | 54 ms | 16512 KB |
oddLoop_1.txt | AC | 31 ms | 11392 KB |
oddLoop_2.txt | AC | 45 ms | 14720 KB |
rnd_0.txt | AC | 48 ms | 9984 KB |
rnd_1.txt | WA | 52 ms | 10368 KB |
rnd_2.txt | WA | 48 ms | 9984 KB |
rnd_3.txt | AC | 51 ms | 10368 KB |
rnd_4.txt | AC | 52 ms | 10112 KB |
rnd_5.txt | AC | 46 ms | 8960 KB |
rnd_6.txt | AC | 50 ms | 9984 KB |
rnd_7.txt | WA | 49 ms | 9728 KB |
rnd_8.txt | AC | 46 ms | 8832 KB |
rnd_9.txt | AC | 38 ms | 7168 KB |
sampleNo.txt | AC | 2 ms | 3712 KB |
samplePath.txt | AC | 2 ms | 3712 KB |
sampleTri.txt | AC | 2 ms | 3712 KB |
star.txt | AC | 41 ms | 9588 KB |
star_0.txt | AC | 41 ms | 9588 KB |
star_1.txt | AC | 41 ms | 9588 KB |
unique_0.txt | WA | 48 ms | 10496 KB |
unique_1.txt | WA | 48 ms | 10496 KB |
unique_2.txt | WA | 48 ms | 10496 KB |
unique_3.txt | WA | 48 ms | 10496 KB |
unique_4.txt | WA | 50 ms | 10496 KB |
unique_5.txt | WA | 48 ms | 10496 KB |
unique_6.txt | WA | 48 ms | 10496 KB |
unique_7.txt | WA | 48 ms | 10496 KB |
unique_8.txt | WA | 48 ms | 10496 KB |
unique_9.txt | WA | 48 ms | 10496 KB |