oj.uz

Submission #418578

# Submission time Handle Problem Language Result Execution time Memory
418578 2021-06-05T14:37:41 Z Berted Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 71528 KB 
#include <iostream>
#include <vector>

#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int INF = 1e9;

int N, M, H[500001];
vector<pii> adj[500001];

bool used[500001];

int DFS(int u)
{
	while (adj[u].size())
	{
		int v = adj[u].back().fst, id = adj[u].back().snd; adj[u].pop_back();
		if (used[id]) continue;

		used[id] = 1;
		if (H[v] < H[u])
		{
			cout << u + 1 << " "; 
			H[u] = INF;
			return H[v];
		}

		H[v] = H[u] + 1;
		int ret = DFS(v);
		if (ret < H[u])
		{
			cout << u + 1 << " ";
			H[u] = INF; 
			return ret;
		}

		if (ret == H[u]) {cout << u + 1 << "\n";}
	}

	H[u] = INF;
	return INF;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) H[i] = INF;
	for (int i = 0; i < M; i++)
	{
		int u, v; cin >> u >> v;
		adj[u - 1].push_back({v - 1, i});
		adj[v - 1].push_back({u - 1, i});
	}
	for (int i = 0; i < N; i++)
	{
		if (adj[i].size()) {H[i] = 0; DFS(i);}
	}
	return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11976 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 8 ms 12064 KB Output is correct
4 Correct 10 ms 12080 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 10 ms 12212 KB Output is correct
7 Correct 14 ms 12660 KB Output is correct
8 Correct 9 ms 12236 KB Output is correct
9 Correct 41 ms 15172 KB Output is correct
10 Correct 10 ms 12108 KB Output is correct
11 Correct 10 ms 12212 KB Output is correct
12 Correct 47 ms 15680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 12064 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 9 ms 12076 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 14 ms 12620 KB Output is correct
8 Correct 9 ms 12208 KB Output is correct
9 Correct 40 ms 15228 KB Output is correct
10 Correct 10 ms 12108 KB Output is correct
11 Correct 10 ms 12108 KB Output is correct
12 Correct 55 ms 15700 KB Output is correct
13 Correct 70 ms 23624 KB Output is correct
14 Correct 62 ms 16964 KB Output is correct
15 Correct 56 ms 16312 KB Output is correct
16 Correct 72 ms 23612 KB Output is correct
17 Correct 66 ms 16928 KB Output is correct
18 Correct 76 ms 18628 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 8 ms 11980 KB Output is correct
3 Correct 8 ms 11980 KB Output is correct
4 Correct 9 ms 12108 KB Output is correct
5 Correct 9 ms 12072 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 13 ms 12716 KB Output is correct
8 Correct 10 ms 12212 KB Output is correct
9 Correct 40 ms 15172 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Correct 10 ms 12128 KB Output is correct
12 Correct 46 ms 15684 KB Output is correct
13 Correct 71 ms 23620 KB Output is correct
14 Correct 60 ms 16976 KB Output is correct
15 Correct 54 ms 16380 KB Output is correct
16 Correct 73 ms 23544 KB Output is correct
17 Correct 65 ms 16836 KB Output is correct
18 Correct 63 ms 18512 KB Output is correct
19 Execution timed out 503 ms 71528 KB Time limit exceeded
20 Halted 0 ms 0 KB -