Submission #136364

#	Time	Username	Problem	Language	Result	Execution time	Memory
136364		tdwn	Senior Postmen (BOI14_postmen)	C++17	55 / 100	869 ms	82680 KiB

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() {
	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);

			reverse(v.begin(), v.end());

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45