Submission #880182


Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
using namespace std;

const int maxn = int(1e5)+5, maxm = int(2e5)+5;

int n, m;
vector<pair<int, int>> graph[maxn];
int vv[maxm];
pair<pair<int, bool>, pair<int, bool>> edge[maxm];

bool vis(int x, int y)
{
	if(edge[y].first.first == x) return edge[y].first.second;
	else return edge[y].second.second;
}

void mark(int x, int y)
{
	if(edge[y].first.first == x) edge[y].first.second = 1;
	else edge[y].second.second = 1;
}

int bfs()
{
	deque<pair<int, pair<int, int>>> Q;
	for(auto it: graph[1])
	{
		Q.push_back({it.first, {it.second, 1}});
	}

	pair<int, pair<int, int>> top; 
	while(!Q.empty())
	{
		top = Q.front();
		Q.pop_front();
		if(vis(top.first, top.second.first)) continue;
		mark(top.first, top.second.first);
		if(top.first == n) return top.second.second;
		for(auto it: graph[top.first])
		{
			if(!vis(it.first, it.second))
			{
				if(vv[top.second.first] == vv[it.second]) Q.push_front({it.first, {it.second, top.second.second}});
				else Q.push_back({it.first, {it.second, top.second.second+1}});
			}
		} 
	}
	return -1;
}

int main(void)
{
	int u, v, c;
	scanf("%d%d", &n, &m);

	for(int i = 0;i < m;i++)
	{
		scanf("%d%d%d", &u, &v, &c);
		graph[u].push_back({v, i});
		graph[v].push_back({u, i});
		vv[i] = c;
		edge[i] = {{u, 0}, {v, 0}};
	}
	printf("%d\n", bfs());
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User NibNalin
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1433 Byte
Status MLE
Exec Time 3313 ms
Memory 1522516 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:57:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
./Main.cpp:61:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &c);
                              ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 25
TLE × 28
MLE × 3
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, 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 8 ms 2560 KB
02.txt AC 160 ms 21648 KB
03.txt AC 209 ms 16256 KB
04.txt AC 155 ms 12672 KB
05.txt AC 219 ms 16896 KB
06.txt AC 81 ms 7680 KB
07.txt AC 94 ms 8704 KB
08.txt AC 199 ms 14720 KB
09.txt AC 94 ms 8832 KB
10.txt AC 98 ms 8832 KB
11.txt TLE 3277 ms 1084180 KB
12.txt AC 270 ms 63928 KB
13.txt TLE 3284 ms 1153116 KB
14.txt MLE 2439 ms 680684 KB
15.txt TLE 3309 ms 1451344 KB
16.txt TLE 3277 ms 1110716 KB
17.txt TLE 3272 ms 1115632 KB
18.txt TLE 3274 ms 1135196 KB
19.txt TLE 3278 ms 1153928 KB
20.txt TLE 3279 ms 1122804 KB
21.txt MLE 981 ms 257944 KB
22.txt TLE 3276 ms 1124068 KB
23.txt AC 339 ms 53772 KB
24.txt TLE 3313 ms 1503620 KB
25.txt AC 308 ms 90628 KB
26.txt TLE 3309 ms 1498892 KB
27.txt AC 232 ms 35900 KB
28.txt TLE 3299 ms 1397668 KB
29.txt TLE 3225 ms 617604 KB
30.txt TLE 3302 ms 1468436 KB
31.txt TLE 3299 ms 1454584 KB
32.txt TLE 3297 ms 1421800 KB
33.txt AC 2639 ms 166028 KB
34.txt TLE 3267 ms 1076036 KB
35.txt AC 309 ms 85532 KB
36.txt TLE 3266 ms 1095468 KB
37.txt MLE 1223 ms 346516 KB
38.txt TLE 3269 ms 1099728 KB
sample_01.txt AC 8 ms 2560 KB
sample_02.txt AC 8 ms 2560 KB
sample_03.txt AC 8 ms 2560 KB
w1.txt TLE 3267 ms 1076008 KB
w10.txt AC 186 ms 11904 KB
w11.txt AC 494 ms 110328 KB
w12.txt AC 488 ms 104740 KB
w13.txt AC 2036 ms 16740 KB
w14.txt AC 255 ms 11904 KB
w15.txt AC 564 ms 120520 KB
w16.txt TLE 3235 ms 745764 KB
w17.txt AC 1064 ms 221592 KB
w18.txt AC 374 ms 12032 KB
w2.txt TLE 3270 ms 1120420 KB
w3.txt TLE 3275 ms 1164312 KB
w4.txt TLE 3307 ms 1522516 KB
w5.txt TLE 3270 ms 1112528 KB
w6.txt TLE 3269 ms 1117168 KB
w7.txt TLE 3250 ms 935972 KB
w8.txt TLE 3166 ms 82224 KB
w9.txt AC 1423 ms 11432 KB