Submission #74661

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

postmen

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

#define getchar_unlocked getchar
#define putchar_unlocked putchar

int in() {
	char c=getchar_unlocked();
	while(c<'0'||c>'9')
		c=getchar_unlocked();
	int r=0;
	while(c>='0'&&c<='9') {
		r=r*10+c-'0';
		c=getchar_unlocked();
	}
	return r;
}

void out(int x) {
	int lz=0, r=0;
	while(x%10==0) {
		++lz;
		x/=10;
	}
	while(x) {
		r=r*10+x%10;
		x/=10;
	}
	while(r) {
		putchar_unlocked('0'+r%10);
		r/=10;
	}
	while(lz--)
		putchar_unlocked('0');
}

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() {
	n=in(), m=in();
	for(int i=0; i<m; ++i) {
		eu[i]=in()-1, ev[i]=in()-1;
		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]) {
				out(a2.back()+1);
				putchar_unlocked(' ');
				b[a2.back()]=0;
				a2.pop_back();
			}
			out(a1[i]+1);
			putchar_unlocked('\n');
		} else {
			a2.push_back(a1[i]);
			b[a1[i]]=1;
		}
	}
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:62: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	12104 KB	Output is correct
2	Correct	13 ms	12136 KB	Output is correct
3	Correct	14 ms	12032 KB	Output is correct
4	Correct	16 ms	12288 KB	Output is correct
5	Correct	14 ms	12160 KB	Output is correct
6	Correct	13 ms	12424 KB	Output is correct
7	Correct	18 ms	13032 KB	Output is correct
8	Correct	14 ms	12288 KB	Output is correct
9	Correct	39 ms	18008 KB	Output is correct
10	Correct	14 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	44 ms	18164 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	12 ms	12136 KB	Output is correct
3	Correct	11 ms	12160 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	16 ms	13056 KB	Output is correct
8	Correct	13 ms	12288 KB	Output is correct
9	Correct	39 ms	18008 KB	Output is correct
10	Correct	15 ms	12288 KB	Output is correct
11	Correct	13 ms	12288 KB	Output is correct
12	Correct	44 ms	18268 KB	Output is correct
13	Correct	84 ms	20988 KB	Output is correct
14	Correct	66 ms	18424 KB	Output is correct
15	Correct	66 ms	19440 KB	Output is correct
16	Correct	88 ms	20832 KB	Output is correct
17	Correct	75 ms	16728 KB	Output is correct
18	Correct	69 ms	19060 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	12104 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	12 ms	12160 KB	Output is correct
6	Correct	15 ms	12416 KB	Output is correct
7	Correct	15 ms	13056 KB	Output is correct
8	Correct	17 ms	12352 KB	Output is correct
9	Correct	50 ms	18028 KB	Output is correct
10	Correct	16 ms	12288 KB	Output is correct
11	Correct	27 ms	12288 KB	Output is correct
12	Correct	44 ms	18228 KB	Output is correct
13	Correct	69 ms	20852 KB	Output is correct
14	Correct	68 ms	18420 KB	Output is correct
15	Correct	66 ms	19440 KB	Output is correct
16	Correct	87 ms	20852 KB	Output is correct
17	Correct	83 ms	16752 KB	Output is correct
18	Correct	91 ms	18932 KB	Output is correct
19	Execution timed out	588 ms	55736 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-