Submission #74658

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
74658	2018-09-05T23:14:21 Z	tmwilliamlin168	Senior Postmen (BOI14_postmen)	C++14	55 / 100	500 ms	55828 KB

postmen

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

const int mxN=5e5;
int n, m, eu[mxN], ev[mxN];
vector<int> adj[mxN], a1, a2;
bool a[mxN], b[mxN];

void dfs(int u) {
	while(adj[u].size()) {
		int e=adj[u].back();
		adj[u].pop_back();
		if(a[e])
			continue;
		a[e]=1;
		dfs(eu[e]^ev[e]^u);
	}
	a1.push_back(u);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<m; ++i) {
		cin >> eu[i] >> ev[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	dfs(0);
	for(int i=0; i<a1.size(); ++i) {
		if(b[a1[i]]) {
			while(a2.back()!=a1[i]) {
				cout << a2.back()+1 << " ";
				b[a2.back()]=0;
				a2.pop_back();
			}
			cout << a1[i]+1 << " \n";
		} else {
			a2.push_back(a1[i]);
			b[a1[i]]=1;
		}
	}
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a1.size(); ++i) {
               ~^~~~~~~~~~

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12212 KB	Output is correct
2	Correct	16 ms	12032 KB	Output is correct
3	Correct	12 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	13 ms	12408 KB	Output is correct
7	Correct	21 ms	13124 KB	Output is correct
8	Correct	15 ms	12288 KB	Output is correct
9	Correct	47 ms	18032 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	53 ms	18296 KB	Output is correct

Subtask #2

17.0 / 17.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	13 ms	12032 KB	Output is correct
4	Correct	12 ms	12288 KB	Output is correct
5	Correct	14 ms	12160 KB	Output is correct
6	Correct	15 ms	12416 KB	Output is correct
7	Correct	21 ms	13184 KB	Output is correct
8	Correct	15 ms	12288 KB	Output is correct
9	Correct	50 ms	18032 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	15 ms	12320 KB	Output is correct
12	Correct	52 ms	18288 KB	Output is correct
13	Correct	98 ms	20848 KB	Output is correct
14	Correct	105 ms	18416 KB	Output is correct
15	Correct	77 ms	19564 KB	Output is correct
16	Correct	96 ms	20852 KB	Output is correct
17	Correct	92 ms	16728 KB	Output is correct
18	Correct	91 ms	19032 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12032 KB	Output is correct
2	Correct	11 ms	12136 KB	Output is correct
3	Correct	12 ms	12032 KB	Output is correct
4	Correct	13 ms	12288 KB	Output is correct
5	Correct	12 ms	12160 KB	Output is correct
6	Correct	21 ms	12392 KB	Output is correct
7	Correct	16 ms	13056 KB	Output is correct
8	Correct	15 ms	12288 KB	Output is correct
9	Correct	49 ms	18008 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	49 ms	18252 KB	Output is correct
13	Correct	97 ms	20868 KB	Output is correct
14	Correct	92 ms	18416 KB	Output is correct
15	Correct	84 ms	19568 KB	Output is correct
16	Correct	131 ms	20896 KB	Output is correct
17	Correct	96 ms	16752 KB	Output is correct
18	Correct	83 ms	19056 KB	Output is correct
19	Execution timed out	577 ms	55828 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-