Submission #74658

#	Time	Username	Problem	Language	Result	Execution time	Memory
74658		tmwilliamlin168	Senior Postmen (BOI14_postmen)	C++14	55 / 100	577 ms	55828 KiB

postmen

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

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 (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a1.size(); ++i) {
               ~^~~~~~~~~~

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