Submission #754856

#	Time	Username	Problem	Language	Result	Execution time	Memory
754856		raysh07	Senior Postmen (BOI14_postmen)	C++17	0 / 100	14 ms	23816 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define INF (int)(1e9)
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
const int N = 5e5 + 69;
set <int> adj[N], c2;
vector <int> c1;
int curr;
int cnt = 0;

void dfs(int u){
	c1.push_back(u);
	c2.insert(u);
	cnt++;
	//cout << u << endl;

	for (int v : adj[u]){
		if (v == curr) {
			adj[u].erase(v);
			adj[v].erase(u);
			break;
		}
		else if (c2.find(v) == c2.end()){
			adj[u].erase(v);
			adj[v].erase(u);
			dfs(v);
			break;
		}
	}
}

void Solve(){
	cin >> n >> m;

	for (int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;

		adj[u].insert(v);
		adj[v].insert(u);
	}

	for (int i = 1; i <= n; i++){
		while (adj[i].size()){
			c1.clear();
			c2.clear();

			int u = i;
			curr = u;
			dfs(u);

			for (auto x : c1) cout << x << " ";
			cout << "\n";
		}
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t = 1; 
	//cin >> t;
	
	while (t--) Solve();
	return 0;
}

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