Submission #136388

#	Time	Username	Problem	Language	Result	Execution time	Memory
136388		tdwn	Senior Postmen (BOI14_postmen)	C++17	100 / 100	450 ms	82576 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;

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');
}

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

	n = in();
	m = in();

	int a, b;
	for(int i=0;i<m;i++) {
		a = in(); b = in();
		
		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;
				out(seq.back());
				putchar_unlocked(' ');
				seq.pop_back();
			} 
			out(i);
			putchar_unlocked('\n');
		}
	} 
}

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