Submission #1733544


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
#define mp2(a,b,c,d) P2(P(a,b),P(c,d))

const ll INF=1000000000000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

vector<P1> G[302];
//bool used[100010];
vector<int> vs;
ll dist[302];
void dfs(int v){
	//if(dist[v] != INF)return;
	//dist[v] = d;
	rep(i,G[v].size()){
		P1 p = G[v][i];
		if(dist[p.sc.fr] == INF){
			dist[p.sc.fr] = dist[v] + p.sc.sc;
			dfs(p.sc.fr);
			//used[p.fr] = true;
			vs.pb(p.fr);
		}
	}
}

void dfs2(int v,int x){
	//if(dist[v] != INF)return;
	//dist[v] = d;
	rep(i,G[v].size()){
		P1 p = G[v][i];
		if(p.fr == x)continue;
		//if(used[p.fr])continue;
		if(dist[p.sc.fr] == INF){
			dist[p.sc.fr] = dist[v] + p.sc.sc;
			dfs2(p.sc.fr,x);
			//vs.pb(p.fr);
		}
	}
}

int main(){
	static int n,m;
	static int a[100010],b[100010];
	static ll c[100010];
	scanf("%d%d",&n,&m);
	rep(i,m){
		scanf("%d%d%lld",&a[i],&b[i],&c[i]);
	}
	
	rep(i,m){
		G[a[i]].pb(mp1(i,b[i],c[i]));
	}
	
	/*rep(i,100010){
		used[i] = false;
	}*/
	rep(i,302){
		dist[i] = INF;
	}
	dist[1] = 0;
	dfs(1);
	
	int cnt = 0;
	rep(i,m){
		if(dist[b[i]]-dist[a[i]] != c[i])cnt ++;
	}
	
	if(cnt <= 1){
		puts("Yes");
		return 0;
	}
	
	rep(x,vs.size()){
		int v = b[vs[x]];
		rep(i,302){
			dist[i] = INF;
		}
		dist[v] = 0;
		dfs2(v,vs[x]);
		cnt = 0;
		rep(i,m){
			if(dist[b[i]]-dist[a[i]] != c[i])cnt ++;
		}
		if(cnt <= 1){
			puts("Yes");
			return 0;
		}
	}
	
	puts("No");
	return 0;
}

Submission Info

Submission Time
Task C - グラフいじり
User yokozuna57
Language C++14 (GCC 5.4.1)
Score 800
Code Size 2429 Byte
Status
Exec Time 113 ms
Memory 7424 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76: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:78:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&a[i],&b[i],&c[i]);
                                      ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2
All 800 / 800 divide2_0, divide2_1, divide2_10, divide2_11, divide2_12, divide2_13, divide2_14, divide2_15, divide2_16, divide2_17, divide2_18, divide2_19, divide2_2, divide2_3, divide2_4, divide2_5, divide2_6, divide2_7, divide2_8, divide2_9, example_0, example_1, example_2, manyerr_0, manyerr_1, manyerr_10, manyerr_11, manyerr_12, manyerr_13, manyerr_14, manyerr_15, manyerr_16, manyerr_17, manyerr_18, manyerr_19, manyerr_2, manyerr_3, manyerr_4, manyerr_5, manyerr_6, manyerr_7, manyerr_8, manyerr_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_10, small_11, small_12, small_13, small_14, small_15, small_16, small_17, small_18, small_19, small_2, small_3, small_4, small_5, small_6, small_7, small_8, small_9
Case Name Status Exec Time Memory
divide2_0 13 ms 2304 KB
divide2_1 16 ms 1024 KB
divide2_10 19 ms 2944 KB
divide2_11 2 ms 384 KB
divide2_12 14 ms 2432 KB
divide2_13 2 ms 384 KB
divide2_14 64 ms 2560 KB
divide2_15 1 ms 256 KB
divide2_16 13 ms 2432 KB
divide2_17 2 ms 384 KB
divide2_18 52 ms 2304 KB
divide2_19 3 ms 384 KB
divide2_2 24 ms 4352 KB
divide2_3 24 ms 1408 KB
divide2_4 14 ms 2432 KB
divide2_5 3 ms 384 KB
divide2_6 54 ms 2432 KB
divide2_7 3 ms 384 KB
divide2_8 15 ms 2560 KB
divide2_9 8 ms 1664 KB
example_0 1 ms 256 KB
example_1 1 ms 256 KB
example_2 1 ms 256 KB
manyerr_0 109 ms 5504 KB
manyerr_1 90 ms 3456 KB
manyerr_10 105 ms 5120 KB
manyerr_11 62 ms 2944 KB
manyerr_12 110 ms 5504 KB
manyerr_13 2 ms 384 KB
manyerr_14 113 ms 5376 KB
manyerr_15 2 ms 384 KB
manyerr_16 111 ms 7424 KB
manyerr_17 3 ms 384 KB
manyerr_18 108 ms 5376 KB
manyerr_19 4 ms 512 KB
manyerr_2 113 ms 5376 KB
manyerr_3 5 ms 512 KB
manyerr_4 106 ms 5248 KB
manyerr_5 61 ms 2816 KB
manyerr_6 106 ms 5120 KB
manyerr_7 1 ms 256 KB
manyerr_8 106 ms 5248 KB
manyerr_9 6 ms 768 KB
rand_0 107 ms 5504 KB
rand_1 5 ms 896 KB
rand_10 27 ms 5120 KB
rand_11 2 ms 384 KB
rand_12 106 ms 5504 KB
rand_13 11 ms 2304 KB
rand_14 109 ms 5376 KB
rand_15 4 ms 640 KB
rand_16 28 ms 5376 KB
rand_17 2 ms 384 KB
rand_18 113 ms 5376 KB
rand_19 3 ms 512 KB
rand_2 28 ms 5504 KB
rand_3 1 ms 256 KB
rand_4 28 ms 5248 KB
rand_5 5 ms 1024 KB
rand_6 27 ms 5120 KB
rand_7 12 ms 2048 KB
rand_8 103 ms 5120 KB
rand_9 2 ms 384 KB
small_0 1 ms 256 KB
small_1 1 ms 256 KB
small_10 1 ms 256 KB
small_11 1 ms 256 KB
small_12 1 ms 256 KB
small_13 1 ms 256 KB
small_14 1 ms 256 KB
small_15 1 ms 256 KB
small_16 1 ms 256 KB
small_17 1 ms 256 KB
small_18 1 ms 256 KB
small_19 1 ms 256 KB
small_2 1 ms 256 KB
small_3 1 ms 256 KB
small_4 1 ms 256 KB
small_5 1 ms 256 KB
small_6 1 ms 256 KB
small_7 1 ms 256 KB
small_8 1 ms 256 KB
small_9 1 ms 256 KB