Submission #31490

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31490	2017-08-29T06:51:09 Z	cheater2k	Senior Postmen (BOI14_postmen)	C++14	55 / 100	500 ms	53240 KB

postmen

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;

int n, m;
vector < pair<int,int> > G[N];
vector <int> E;
bool del[N];
int pos[N];

void dfs(int u) {
	while(!G[u].empty()) {
		int id = G[u].back().first, v = G[u].back().second;
		if (del[id]) { G[u].pop_back(); continue; }
		else del[id] = 1, dfs(v);
	}
	E.push_back(u);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(make_pair(i,v));
		G[v].push_back(make_pair(i,u));
	}

	dfs(1);
	//for (int u: E) cerr << u << ' '; cerr << endl;

	stack <int> s;

	for (int i = 0; i < (int)E.size(); ++i) {
		int u = E[i];
		if (!pos[u]) {
			pos[u] = 1;
			s.push(u);
		} else {
			printf("%d ", u);
			while(s.top() != u) {
				printf("%d ", s.top());
				pos[s.top()] = 0;
				s.pop();
			}
			printf("\n");
		}
	}
}

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12032 KB	Output is correct
2	Correct	12 ms	12032 KB	Output is correct
3	Correct	12 ms	12032 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	13 ms	12160 KB	Output is correct
6	Correct	14 ms	12340 KB	Output is correct
7	Correct	17 ms	13184 KB	Output is correct
8	Correct	15 ms	12264 KB	Output is correct
9	Correct	53 ms	18248 KB	Output is correct
10	Correct	16 ms	12264 KB	Output is correct
11	Correct	14 ms	12264 KB	Output is correct
12	Correct	54 ms	18512 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12032 KB	Output is correct
2	Correct	12 ms	12032 KB	Output is correct
3	Correct	12 ms	12032 KB	Output is correct
4	Correct	14 ms	12340 KB	Output is correct
5	Correct	15 ms	12136 KB	Output is correct
6	Correct	13 ms	12416 KB	Output is correct
7	Correct	25 ms	13184 KB	Output is correct
8	Correct	14 ms	12288 KB	Output is correct
9	Correct	47 ms	18260 KB	Output is correct
10	Correct	16 ms	12288 KB	Output is correct
11	Correct	16 ms	12288 KB	Output is correct
12	Correct	75 ms	18524 KB	Output is correct
13	Correct	149 ms	20288 KB	Output is correct
14	Correct	98 ms	18288 KB	Output is correct
15	Correct	90 ms	19540 KB	Output is correct
16	Correct	93 ms	20312 KB	Output is correct
17	Correct	125 ms	16604 KB	Output is correct
18	Correct	94 ms	18836 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12032 KB	Output is correct
2	Correct	14 ms	12032 KB	Output is correct
3	Correct	17 ms	12160 KB	Output is correct
4	Correct	14 ms	12324 KB	Output is correct
5	Correct	14 ms	12160 KB	Output is correct
6	Correct	16 ms	12416 KB	Output is correct
7	Correct	16 ms	13184 KB	Output is correct
8	Correct	12 ms	12264 KB	Output is correct
9	Correct	57 ms	18176 KB	Output is correct
10	Correct	18 ms	12288 KB	Output is correct
11	Correct	16 ms	12284 KB	Output is correct
12	Correct	71 ms	18628 KB	Output is correct
13	Correct	107 ms	20312 KB	Output is correct
14	Correct	111 ms	18164 KB	Output is correct
15	Correct	88 ms	19652 KB	Output is correct
16	Correct	91 ms	20236 KB	Output is correct
17	Correct	83 ms	16628 KB	Output is correct
18	Correct	90 ms	18872 KB	Output is correct
19	Execution timed out	529 ms	53240 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-