Submission #3238498
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); } for(auto &it:adj[cur]) { 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 { l[it.second] = max(l[it.second],sum-cost[it.second]-r[cur]); r[it.second] = min(r[it.second],sum-cost[it.second]-l[cur]); } } else { if(it.first+sum-cost[it.second]<=0 || (it.first + sum-cost[it.second])%2!=0) f=0; else { l[it.second] = max(l[it.second],(it.first+sum-cost[it.second])/2); r[it.second] = min(r[it.second],(it.first+sum-cost[it.second])/2); } } } } if(d%2==0) { l[1] = max(l[1], sum+l[cur]); r[1] = min(r[1], sum+r[cur]); } else { l[1] = max(l[1], sum-r[cur]); r[1] = min(r[1], sum-l[cur]); } } 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]) puts("0"); else printf("%lld\n",max(0ll,r[1]-l[1]+1)); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - + Graph |
User | vjudge2 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1737 Byte |
Status | WA |
Exec Time | 57 ms |
Memory | 18176 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:53: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:55: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 | 9856 KB |
OK_1.txt | AC | 42 ms | 9856 KB |
OK_2.txt | AC | 43 ms | 9856 KB |
OK_3.txt | AC | 42 ms | 9856 KB |
OK_4.txt | AC | 43 ms | 9856 KB |
close_0.txt | AC | 52 ms | 11136 KB |
close_1.txt | WA | 51 ms | 10624 KB |
close_2.txt | AC | 51 ms | 10880 KB |
close_3.txt | AC | 52 ms | 9856 KB |
close_4.txt | AC | 51 ms | 9984 KB |
many_0.txt | AC | 49 ms | 10240 KB |
many_1.txt | AC | 51 ms | 10496 KB |
many_2.txt | AC | 54 ms | 10624 KB |
many_3.txt | AC | 53 ms | 10752 KB |
many_4.txt | AC | 53 ms | 10752 KB |
many_5.txt | AC | 53 ms | 10752 KB |
many_6.txt | AC | 52 ms | 10496 KB |
many_7.txt | AC | 51 ms | 10368 KB |
max.txt | WA | 30 ms | 5632 KB |
maxBip.txt | AC | 38 ms | 7296 KB |
multiple_0.txt | WA | 49 ms | 10240 KB |
multiple_1.txt | WA | 51 ms | 10368 KB |
multiple_2.txt | WA | 52 ms | 10624 KB |
multiple_3.txt | WA | 53 ms | 10624 KB |
multiple_4.txt | WA | 53 ms | 10752 KB |
multiple_5.txt | WA | 53 ms | 10752 KB |
multiple_6.txt | WA | 52 ms | 10624 KB |
multiple_7.txt | WA | 51 ms | 10368 KB |
oddLoop.txt | AC | 57 ms | 18176 KB |
oddLoop_0.txt | AC | 57 ms | 18048 KB |
oddLoop_1.txt | AC | 32 ms | 12288 KB |
oddLoop_2.txt | AC | 48 ms | 16000 KB |
rnd_0.txt | AC | 48 ms | 9984 KB |
rnd_1.txt | WA | 53 ms | 10624 KB |
rnd_2.txt | WA | 49 ms | 10112 KB |
rnd_3.txt | AC | 52 ms | 10624 KB |
rnd_4.txt | AC | 53 ms | 10368 KB |
rnd_5.txt | AC | 48 ms | 9344 KB |
rnd_6.txt | AC | 51 ms | 10112 KB |
rnd_7.txt | WA | 50 ms | 9984 KB |
rnd_8.txt | AC | 48 ms | 8960 KB |
rnd_9.txt | AC | 39 ms | 7296 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 | 50 ms | 10880 KB |
unique_1.txt | WA | 50 ms | 10880 KB |
unique_2.txt | WA | 50 ms | 11008 KB |
unique_3.txt | WA | 50 ms | 10880 KB |
unique_4.txt | WA | 50 ms | 10880 KB |
unique_5.txt | WA | 53 ms | 10880 KB |
unique_6.txt | WA | 51 ms | 10880 KB |
unique_7.txt | WA | 50 ms | 10880 KB |
unique_8.txt | WA | 50 ms | 10880 KB |
unique_9.txt | WA | 50 ms | 10880 KB |