Submission #211568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211568	2020-03-20T17:29:22 Z	admin	Senior Postmen (BOI14_postmen)	C++14	100 / 100	462 ms	57592 KB

postmen

#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int, int>> graph[500001];
bool visited[500001], used[500001];
int nxt[500001];
 
void dfs(int node) {
	if (visited[node]) {
		while (visited[node]) {
			visited[node] = false;
			cout << node << ' ';
			node = nxt[node];
		}
		cout << '\n';
	}
	while (graph[node].size()) {
		int c, idx;
		tie(c, idx) = graph[node].back();
		graph[node].pop_back();
		if (!used[idx]) {
			used[idx] = true;
			visited[node] = true;
			nxt[node] = c;
			dfs(c);
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back({b, i});
		graph[b].push_back({a, i});
	}
	
	dfs(1);
	return 0;
}

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12032 KB	Output is correct
2	Correct	13 ms	12032 KB	Output is correct
3	Correct	12 ms	12160 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	15 ms	12160 KB	Output is correct
6	Correct	13 ms	12416 KB	Output is correct
7	Correct	17 ms	13312 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	44 ms	19192 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	16 ms	12288 KB	Output is correct
12	Correct	48 ms	19576 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12032 KB	Output is correct
2	Correct	11 ms	12160 KB	Output is correct
3	Correct	12 ms	12032 KB	Output is correct
4	Correct	18 ms	12288 KB	Output is correct
5	Correct	17 ms	12160 KB	Output is correct
6	Correct	13 ms	12416 KB	Output is correct
7	Correct	16 ms	13312 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	45 ms	19192 KB	Output is correct
10	Correct	12 ms	12288 KB	Output is correct
11	Correct	12 ms	12288 KB	Output is correct
12	Correct	62 ms	19580 KB	Output is correct
13	Correct	85 ms	21112 KB	Output is correct
14	Correct	73 ms	18424 KB	Output is correct
15	Correct	62 ms	20436 KB	Output is correct
16	Correct	81 ms	21112 KB	Output is correct
17	Correct	75 ms	16248 KB	Output is correct
18	Correct	80 ms	19704 KB	Output is correct

Subtask #3

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12160 KB	Output is correct
2	Correct	12 ms	12160 KB	Output is correct
3	Correct	11 ms	12032 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	12 ms	12160 KB	Output is correct
6	Correct	12 ms	12416 KB	Output is correct
7	Correct	17 ms	13312 KB	Output is correct
8	Correct	13 ms	12288 KB	Output is correct
9	Correct	46 ms	19192 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	12 ms	12288 KB	Output is correct
12	Correct	51 ms	19576 KB	Output is correct
13	Correct	68 ms	21112 KB	Output is correct
14	Correct	64 ms	18424 KB	Output is correct
15	Correct	69 ms	20332 KB	Output is correct
16	Correct	69 ms	21112 KB	Output is correct
17	Correct	69 ms	16248 KB	Output is correct
18	Correct	67 ms	19576 KB	Output is correct
19	Correct	459 ms	57592 KB	Output is correct
20	Correct	425 ms	44000 KB	Output is correct
21	Correct	392 ms	53468 KB	Output is correct
22	Correct	454 ms	57592 KB	Output is correct
23	Correct	183 ms	46584 KB	Output is correct
24	Correct	462 ms	33528 KB	Output is correct
25	Correct	454 ms	49828 KB	Output is correct