Submission #31480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31480	2017-08-29T06:44:45 Z	cheater2k	Senior Postmen (BOI14_postmen)	C++14	55 / 100	500 ms	53332 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] = i + 1;
			s.push(i);
			continue;
		} else {
			int stop = pos[u] - 1;
			while(!s.empty()) {
				int t = s.top();
				printf("%d ", E[t]);
				pos[E[t]] = 0;
				s.pop();
				if (t == stop) break;
			}
			printf("\n");
			s.push(i);
			pos[u] = i + 1;
		}
	}
}

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	12032 KB	Output is correct
2	Correct	13 ms	12136 KB	Output is correct
3	Correct	14 ms	12136 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	12 ms	12160 KB	Output is correct
6	Correct	17 ms	12488 KB	Output is correct
7	Correct	17 ms	13184 KB	Output is correct
8	Correct	12 ms	12288 KB	Output is correct
9	Correct	46 ms	18156 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	12 ms	12288 KB	Output is correct
12	Correct	49 ms	18572 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12160 KB	Output is correct
2	Correct	12 ms	12032 KB	Output is correct
3	Correct	11 ms	12032 KB	Output is correct
4	Correct	15 ms	12288 KB	Output is correct
5	Correct	14 ms	12148 KB	Output is correct
6	Correct	13 ms	12416 KB	Output is correct
7	Correct	17 ms	13184 KB	Output is correct
8	Correct	17 ms	12288 KB	Output is correct
9	Correct	47 ms	18172 KB	Output is correct
10	Correct	14 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	59 ms	18508 KB	Output is correct
13	Correct	83 ms	20336 KB	Output is correct
14	Correct	84 ms	18160 KB	Output is correct
15	Correct	80 ms	19668 KB	Output is correct
16	Correct	74 ms	20208 KB	Output is correct
17	Correct	91 ms	16604 KB	Output is correct
18	Correct	74 ms	18928 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12160 KB	Output is correct
2	Correct	13 ms	12032 KB	Output is correct
3	Correct	14 ms	12148 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	12 ms	12160 KB	Output is correct
6	Correct	13 ms	12416 KB	Output is correct
7	Correct	18 ms	13160 KB	Output is correct
8	Correct	14 ms	12288 KB	Output is correct
9	Correct	48 ms	18172 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	14 ms	12264 KB	Output is correct
12	Correct	51 ms	18552 KB	Output is correct
13	Correct	99 ms	20196 KB	Output is correct
14	Correct	84 ms	18160 KB	Output is correct
15	Correct	91 ms	19564 KB	Output is correct
16	Correct	89 ms	20260 KB	Output is correct
17	Correct	83 ms	16628 KB	Output is correct
18	Correct	83 ms	18800 KB	Output is correct
19	Correct	494 ms	53220 KB	Output is correct
20	Correct	472 ms	42700 KB	Output is correct
21	Correct	457 ms	49308 KB	Output is correct
22	Correct	496 ms	53332 KB	Output is correct
23	Correct	208 ms	40936 KB	Output is correct
24	Execution timed out	524 ms	34620 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-