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
AC × 3
AC × 35
WA × 23
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