Submission #2860743


Source Code Expand

#include<bits/stdc++.h>
#define inf 1e8
using namespace std;
struct edge{
	int c,u,v;
	edge(int a,int b,int d):u(a),v(b),c(d) {}
};
vector<edge> e; bool vis[200005];
set<int> adj[300005];
vector<int> g[300005];
int par[300005],dis[300005],n,m;
void init(){
	for(int i=0;i<=300005;i++){
		par[i]=i; 
		dis[i]=1e8;
	}
}
int find(int i){
	if(par[i]==i) return par[i];
	return par[i]=find(par[i]);
}
void dsu(int i,int j){
	par[find(i)]=find(j);
}
void bfs(){
	dis[1]=0;
	queue<int> q; q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(set<int>::iterator it=adj[u].begin();it!=adj[u].end();it++){
			if(dis[*it]>dis[u]+1){
				dis[*it]=min(dis[*it],dis[u]+1);
				q.push(*it);
			}
		}
	}
	if(dis[n]==inf){
	 	cout<<"-1";  
		exit(0);
	}
	else cout<<dis[n]/2; exit(0);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int  i=1; i<=m; i++){
		int c,u,v;
		cin>>u>>v>>c;
		g[u].push_back(e.size());
		g[v].push_back(e.size());
		e.push_back(edge(u,v,c));
	}
	init();
	for(int i=0;i<e.size();i++){
		int u=e[i].u;
		for(int j: g[u]){
			if(!vis[j]){
				if(e[j].c==e[i].c&&i!=j){
					dsu(i,j);
				}
			}
		}
		int v=e[i].v;
		for(int j: g[v]){
			if(!vis[j]){
				if(e[j].c == e[i].c&&i!=j){
					dsu(i,j);
				}
			}
		}
		vis[i]=1;
	}
	for(int i=0;i<e.size();i++){
		adj[par[i]+n+1].insert(e[i].u);
		adj[par[i]+n+1].insert(e[i].v);
		adj[e[i].v].insert(par[i]+1+n);
		adj[e[i].u].insert(par[i]+1+n);
	}
	bfs();
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User haimeo1201
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1539 Byte
Status WA
Exec Time 3160 ms
Memory 68912 KB

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:14:11: warning: iteration 300005u invokes undefined behavior [-Waggressive-loop-optimizations]
   par[i]=i; 
           ^
./Main.cpp:13:15: note: containing loop
  for(int i=0;i<=300005;i++){
               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 18
WA × 8
TLE × 33
Set Name Test Cases
Sample
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt
Case Name Status Exec Time Memory
01.txt AC 10 ms 23680 KB
02.txt AC 709 ms 61360 KB
03.txt AC 302 ms 68272 KB
04.txt AC 241 ms 68016 KB
05.txt WA 292 ms 63024 KB
06.txt WA 96 ms 45748 KB
07.txt WA 114 ms 46772 KB
08.txt AC 269 ms 68912 KB
09.txt AC 122 ms 49076 KB
10.txt AC 120 ms 49076 KB
11.txt TLE 3156 ms 29744 KB
12.txt TLE 3156 ms 28976 KB
13.txt TLE 3156 ms 28716 KB
14.txt WA 1611 ms 54960 KB
15.txt TLE 3156 ms 30000 KB
16.txt TLE 3156 ms 30256 KB
17.txt TLE 3156 ms 29868 KB
18.txt TLE 3156 ms 28592 KB
19.txt TLE 3156 ms 30376 KB
20.txt WA 2156 ms 52144 KB
21.txt TLE 3156 ms 29872 KB
22.txt TLE 3160 ms 29740 KB
23.txt AC 244 ms 60080 KB
24.txt TLE 3156 ms 30768 KB
25.txt TLE 3156 ms 28720 KB
26.txt TLE 3156 ms 29740 KB
27.txt AC 1750 ms 48816 KB
28.txt TLE 3156 ms 30000 KB
29.txt TLE 3156 ms 30000 KB
30.txt TLE 3156 ms 30380 KB
31.txt TLE 3156 ms 29104 KB
32.txt TLE 3156 ms 30888 KB
33.txt TLE 3156 ms 30000 KB
34.txt TLE 3156 ms 29744 KB
35.txt TLE 3156 ms 28976 KB
36.txt TLE 3156 ms 28716 KB
37.txt WA 675 ms 59184 KB
38.txt TLE 3156 ms 29872 KB
sample_01.txt AC 9 ms 23680 KB
sample_02.txt AC 9 ms 23680 KB
sample_03.txt AC 9 ms 23680 KB
w1.txt TLE 3156 ms 30256 KB
w10.txt AC 275 ms 66480 KB
w11.txt TLE 3156 ms 28464 KB
w12.txt AC 1573 ms 35888 KB
w13.txt WA 383 ms 50736 KB
w14.txt AC 286 ms 63152 KB
w15.txt TLE 3156 ms 29104 KB
w16.txt TLE 3156 ms 28208 KB
w17.txt AC 564 ms 31920 KB
w18.txt WA 249 ms 45616 KB
w2.txt TLE 3156 ms 31152 KB
w3.txt TLE 3156 ms 30768 KB
w4.txt TLE 3156 ms 31536 KB
w5.txt TLE 3156 ms 31024 KB
w6.txt TLE 3156 ms 30384 KB
w7.txt TLE 3156 ms 28464 KB
w8.txt AC 1759 ms 65456 KB
w9.txt AC 454 ms 65712 KB