Submission #136378

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136378	2019-07-25T08:04:40 Z	tdwn	Senior Postmen (BOI14_postmen)	C++17	55 / 100	500 ms	82552 KB

postmen

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
const int maxn = 500100;

class edge {
public:
	int nxt_node;
	list<edge>::iterator reverse_edge;

	edge(int _node) {
		nxt_node = _node;
	}
};

list<edge>adj[maxn];
int n, m;

vector<int>euler_tour;
bool visited[maxn];

void solve(int node) {
	while(adj[node].size() > 0) {
		edge x = adj[node].front();
		int nxt = x.nxt_node;

		adj[nxt].erase(x.reverse_edge);
		adj[node].pop_front();

		solve(nxt);
	}
	euler_tour.pb(node);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;

	int a, b;
	for(int i=0;i<m;i++) {
		cin>>a>>b;
		
		adj[a].pf(edge(b));
		list<edge>::iterator it_a = adj[a].begin();
		adj[b].pf(edge(a));
		list<edge>::iterator it_b = adj[b].begin();

		it_a->reverse_edge = it_b;
		it_b->reverse_edge = it_a;
	}
	solve(1);

	vector<int>seq;
	for(int i:euler_tour) {
		//cout<<i<<" ";
		if(!visited[i]) {
			seq.pb(i);
			visited[i] = true;
		}
		else {
			// go back in seq while you find i
			while(seq.size() > 0 && seq.back() != i) {
				visited[seq.back()] = false;
				cout<<seq.back()<<" ";
				seq.pop_back();
			} cout<<i<<"\n";
		}
	} 
}

Subtask #1

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12160 KB	Output is correct
2	Correct	14 ms	12160 KB	Output is correct
3	Correct	12 ms	12032 KB	Output is correct
4	Correct	15 ms	12544 KB	Output is correct
5	Correct	14 ms	12288 KB	Output is correct
6	Correct	17 ms	12672 KB	Output is correct
7	Correct	19 ms	14208 KB	Output is correct
8	Correct	13 ms	12416 KB	Output is correct
9	Correct	68 ms	26104 KB	Output is correct
10	Correct	15 ms	12416 KB	Output is correct
11	Correct	13 ms	12416 KB	Output is correct
12	Correct	71 ms	26208 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12032 KB	Output is correct
2	Correct	11 ms	12032 KB	Output is correct
3	Correct	12 ms	12160 KB	Output is correct
4	Correct	15 ms	12520 KB	Output is correct
5	Correct	15 ms	12288 KB	Output is correct
6	Correct	16 ms	12672 KB	Output is correct
7	Correct	19 ms	14208 KB	Output is correct
8	Correct	12 ms	12356 KB	Output is correct
9	Correct	67 ms	26104 KB	Output is correct
10	Correct	14 ms	12544 KB	Output is correct
11	Correct	13 ms	12416 KB	Output is correct
12	Correct	72 ms	26104 KB	Output is correct
13	Correct	110 ms	26104 KB	Output is correct
14	Correct	105 ms	24184 KB	Output is correct
15	Correct	103 ms	26212 KB	Output is correct
16	Correct	112 ms	26208 KB	Output is correct
17	Correct	107 ms	23036 KB	Output is correct
18	Correct	108 ms	25704 KB	Output is correct

Subtask #3

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	12032 KB	Output is correct
2	Correct	11 ms	12140 KB	Output is correct
3	Correct	11 ms	12032 KB	Output is correct
4	Correct	17 ms	12544 KB	Output is correct
5	Correct	12 ms	12288 KB	Output is correct
6	Correct	15 ms	12672 KB	Output is correct
7	Correct	23 ms	14208 KB	Output is correct
8	Correct	16 ms	12416 KB	Output is correct
9	Correct	62 ms	26104 KB	Output is correct
10	Correct	13 ms	12416 KB	Output is correct
11	Correct	17 ms	12416 KB	Output is correct
12	Correct	69 ms	26104 KB	Output is correct
13	Correct	106 ms	26128 KB	Output is correct
14	Correct	96 ms	24184 KB	Output is correct
15	Correct	97 ms	26104 KB	Output is correct
16	Correct	109 ms	26212 KB	Output is correct
17	Correct	97 ms	23132 KB	Output is correct
18	Correct	106 ms	25600 KB	Output is correct
19	Execution timed out	560 ms	82552 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-