oj.uz

Submission #997179

# Submission time Handle Problem Language Result Execution time Memory
997179 2024-06-11T19:30:17 Z mkola Senior Postmen (BOI14_postmen) C++14
100 / 100
 279 ms 69804 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz size
#define all(x) begin(x), end(x)

#define ll long long

#define INF 1e18
#define MOD (int)(1e9 + 7)

int N, M, cnt[500005];
vector<pair<int, int>> adj[500005];
vector<int> cycle;
vector<vector<int>> ans; 

bool seen[500005];

void dfs(int v) {
	while(adj[v].sz()) {
		pair<int, int> p = adj[v].back();
		adj[v].pop_back();
		int u = p.first, id = p.second;
		if(!seen[id]) {
			seen[id] = true;
			dfs(u);
		}
	}
	cycle.pb(v);
}

int main() {
	ios_base::sync_with_stdio(0); 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});
	}
	dfs(1);
	// 1 5 8 10 9 2 3 6 7 8 4 7 5 4 3 1
	stack<int> st;
	for(int i = 0; i < (int)cycle.sz(); ++i) {
		int v = cycle[i];
		cnt[v]++;
		if(cnt[v] > 1) {
			vector<int> cyc;
			while(st.top() != v) {
				cyc.pb(st.top());
				cnt[st.top()]--;
				st.pop();
			}
			st.pop();
			cnt[v]--;
			cyc.pb(v);
			ans.pb(cyc);
		}
		st.push(v);
	}
	for(auto const &p : ans) {
		for(int v : p)
			cout << v << ' ';
		cout << '\n';
	}
	return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 5 ms 14172 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 25 ms 21288 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 36 ms 21884 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 6 ms 14168 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 27 ms 21460 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 30 ms 21712 KB Output is correct
13 Correct 33 ms 23744 KB Output is correct
14 Correct 35 ms 21312 KB Output is correct
15 Correct 34 ms 24004 KB Output is correct
16 Correct 34 ms 23752 KB Output is correct
17 Correct 35 ms 20044 KB Output is correct
18 Correct 47 ms 22916 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 13144 KB Output is correct
7 Correct 5 ms 14172 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 24 ms 21240 KB Output is correct
10 Correct 3 ms 12796 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 26 ms 21928 KB Output is correct
13 Correct 37 ms 23756 KB Output is correct
14 Correct 34 ms 21320 KB Output is correct
15 Correct 42 ms 23824 KB Output is correct
16 Correct 34 ms 23748 KB Output is correct
17 Correct 35 ms 19956 KB Output is correct
18 Correct 46 ms 22856 KB Output is correct
19 Correct 277 ms 69784 KB Output is correct
20 Correct 202 ms 58456 KB Output is correct
21 Correct 257 ms 69804 KB Output is correct
22 Correct 232 ms 69780 KB Output is correct
23 Correct 113 ms 54480 KB Output is correct
24 Correct 248 ms 52272 KB Output is correct
25 Correct 279 ms 65468 KB Output is correct