Submission #743404

#	Time	Username	Problem	Language	Result	Execution time	Memory
743404		Dan4Life	Senior Postmen (BOI14_postmen)	C++17	100 / 100	442 ms	68944 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define pb push_back
const int mxN = (int)5e5+10;
int n, m, vis[mxN], vis1[mxN], nx[mxN];
vector<pair<int,int>> v, adj[mxN];
int SZ[mxN];

void dfs(int s){
	if(vis[s]){ int p = s;
		while(vis[p]) cout<<p<<" ", vis[p]=0, p = nx[p];
		cout << "\n";
	} 
	while(SZ[s]){
		auto [u,e] = adj[s][SZ[s]-1]; SZ[s]--;
		if(!vis1[e]) vis1[e]=vis[s]=1, nx[s]=u, dfs(u);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		adj[a].pb({b,i}); adj[b].pb({a,i});
	}
	for(int i = 1; i <= n; i++) SZ[i] = sz(adj[i]);
	dfs(1);
}

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