oj.uz

Submission #754856

# Submission time Handle Problem Language Result Execution time Memory
754856 2023-06-08T18:11:29 Z raysh07 Senior Postmen (BOI14_postmen) C++17
0 / 100
 14 ms 23816 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 11 ms 23764 KB Edge does not exist or used 3, 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 23776 KB Edge does not exist or used 3, 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23816 KB Output is correct
2 Incorrect 13 ms 23764 KB Edge does not exist or used 3, 6
3 Halted 0 ms 0 KB -