oj.uz

답안 #136361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136361 2019-07-25T07:50:55 Z tdwn 어르신 집배원 (BOI14_postmen) C++17
55 / 100
 500 ms 82536 KB 
#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() {
	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) {
		if(!visited[i]) {
			seq.pb(i);
			visited[i] = true;
		}
		else {
			// go back in seq while you find i
			vector<int>v;
			while(seq.size() > 0 && seq.back() != i) {
				v.pb(seq.back());
				visited[seq.back()] = false;
				seq.pop_back();
			} v.pb(i);

			for(int i:v) {
				cout<<i<<" ";
			} cout<<"\n";
		}
	} cout<<"\n";
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12032 KB Output is correct
2 Correct 13 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 19 ms 12416 KB Output is correct
5 Correct 16 ms 12288 KB Output is correct
6 Correct 17 ms 12648 KB Output is correct
7 Correct 29 ms 14200 KB Output is correct
8 Correct 14 ms 12288 KB Output is correct
9 Correct 119 ms 26232 KB Output is correct
10 Correct 16 ms 12392 KB Output is correct
11 Correct 15 ms 12416 KB Output is correct
12 Correct 129 ms 26104 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12032 KB Output is correct
2 Correct 12 ms 12032 KB Output is correct
3 Correct 14 ms 12032 KB Output is correct
4 Correct 14 ms 12416 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 17 ms 12648 KB Output is correct
7 Correct 28 ms 14208 KB Output is correct
8 Correct 14 ms 12288 KB Output is correct
9 Correct 117 ms 26044 KB Output is correct
10 Correct 19 ms 12416 KB Output is correct
11 Correct 15 ms 12416 KB Output is correct
12 Correct 123 ms 26232 KB Output is correct
13 Correct 177 ms 26196 KB Output is correct
14 Correct 175 ms 24228 KB Output is correct
15 Correct 157 ms 26268 KB Output is correct
16 Correct 166 ms 26080 KB Output is correct
17 Correct 251 ms 23072 KB Output is correct
18 Correct 171 ms 25712 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12012 KB Output is correct
2 Correct 15 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 18 ms 12416 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 20 ms 12648 KB Output is correct
7 Correct 29 ms 14128 KB Output is correct
8 Correct 14 ms 12392 KB Output is correct
9 Correct 117 ms 26104 KB Output is correct
10 Correct 14 ms 12416 KB Output is correct
11 Correct 19 ms 12416 KB Output is correct
12 Correct 130 ms 26084 KB Output is correct
13 Correct 172 ms 26156 KB Output is correct
14 Correct 170 ms 24180 KB Output is correct
15 Correct 149 ms 26080 KB Output is correct
16 Correct 178 ms 26104 KB Output is correct
17 Correct 195 ms 23040 KB Output is correct
18 Correct 170 ms 25712 KB Output is correct
19 Execution timed out 886 ms 82536 KB Time limit exceeded
20 Halted 0 ms 0 KB -