Submission #74660

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

postmen

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

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() {
	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: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	11 ms	12032 KB	Output is correct
2	Correct	14 ms	12032 KB	Output is correct
3	Correct	15 ms	12032 KB	Output is correct
4	Correct	17 ms	12288 KB	Output is correct
5	Correct	11 ms	12160 KB	Output is correct
6	Correct	16 ms	12416 KB	Output is correct
7	Correct	20 ms	13056 KB	Output is correct
8	Correct	13 ms	12288 KB	Output is correct
9	Correct	45 ms	18032 KB	Output is correct
10	Correct	13 ms	12288 KB	Output is correct
11	Correct	14 ms	12288 KB	Output is correct
12	Correct	59 ms	18392 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	12160 KB	Output is correct
2	Correct	12 ms	12160 KB	Output is correct
3	Correct	14 ms	12032 KB	Output is correct
4	Correct	15 ms	12288 KB	Output is correct
5	Correct	13 ms	12160 KB	Output is correct
6	Correct	16 ms	12468 KB	Output is correct
7	Correct	17 ms	13056 KB	Output is correct
8	Correct	13 ms	12288 KB	Output is correct
9	Correct	58 ms	17968 KB	Output is correct
10	Correct	13 ms	12372 KB	Output is correct
11	Correct	17 ms	12264 KB	Output is correct
12	Correct	80 ms	18244 KB	Output is correct
13	Correct	102 ms	20828 KB	Output is correct
14	Correct	95 ms	18420 KB	Output is correct
15	Correct	84 ms	19544 KB	Output is correct
16	Correct	92 ms	20840 KB	Output is correct
17	Correct	94 ms	16752 KB	Output is correct
18	Correct	81 ms	18928 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12160 KB	Output is correct
2	Correct	12 ms	12208 KB	Output is correct
3	Correct	15 ms	12032 KB	Output is correct
4	Correct	13 ms	12416 KB	Output is correct
5	Correct	15 ms	12212 KB	Output is correct
6	Correct	21 ms	12416 KB	Output is correct
7	Correct	17 ms	13056 KB	Output is correct
8	Correct	22 ms	12288 KB	Output is correct
9	Correct	54 ms	18032 KB	Output is correct
10	Correct	14 ms	12288 KB	Output is correct
11	Correct	12 ms	12288 KB	Output is correct
12	Correct	56 ms	18288 KB	Output is correct
13	Correct	96 ms	20848 KB	Output is correct
14	Correct	95 ms	18392 KB	Output is correct
15	Correct	79 ms	19520 KB	Output is correct
16	Correct	86 ms	20848 KB	Output is correct
17	Correct	91 ms	16728 KB	Output is correct
18	Correct	78 ms	19020 KB	Output is correct
19	Execution timed out	580 ms	55752 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-