oj.uz

Submission #530874

# Submission time Handle Problem Language Result Execution time Memory
530874 2022-02-27T04:11:14 Z hohohaha Senior Postmen (BOI14_postmen) C++14
100 / 100
 449 ms 92336 KB 
#include<bits/stdc++.h> 
using namespace std; 
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
#define ford(i, a, b) for(int i = (int) (b); i >= (int) (a); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
#define int long long
const int maxn = 5e5 + 5; 
int n, m;
vector<ii> g[maxn]; 
bool used[maxn]; 
int pt[maxn]; 
vector<int> ans; 
void dfs(int); 
vector<vi> decompose(); 
bool vs[maxn]; 
void dfs(int u) { 
	while(pt[u] < g[u].size()) {
		int id = g[u][pt[u]].se, v = g[u][pt[u]].fi; 
		if(!used[id]) { 
			used[id] = 1; 
			dfs(v); 
		}
		++pt[u]; 
	}
	ans.eb(u); 
//	cout << u << endl; 
}
vector<vi> decompose() { 
	stack<int> cur; 
	vector<vi> re; 
	for(int u: ans) { 
		if(!vs[u]) { 
			cur.push(u); 
			vs[u] = 1; 
		}
		else { 
			vi cyc; 
			while(vs[u]) { 
				cyc.eb(cur.top()); 
				vs[cur.top()] = 0; 
				cur.pop(); 
			}
			re.eb(cyc); 
			cur.push(u); 
			vs[u] = 1; 
		}
	}
	return re; 		
}
signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m; 
	fori(i, 1, m) { 
		int u, v; cin >> u >> v; 
		g[u].eb(v, i); 
		g[v].eb(u, i); 
	}
	dfs(1); // since the thing is connected
	auto t = decompose(); 
	for(auto cyc: t) { 
		for(int u: cyc) { 
			cout << u << sp; 
		}
		cout << endl; 
	}
}

Compilation message

postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:23:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  while(pt[u] < g[u].size()) {
      |        ~~~~~~^~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 8 ms 12492 KB Output is correct
5 Correct 9 ms 12108 KB Output is correct
6 Correct 11 ms 12620 KB Output is correct
7 Correct 11 ms 14028 KB Output is correct
8 Correct 7 ms 12364 KB Output is correct
9 Correct 36 ms 22584 KB Output is correct
10 Correct 8 ms 12364 KB Output is correct
11 Correct 8 ms 12364 KB Output is correct
12 Correct 45 ms 23236 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 6 ms 11992 KB Output is correct
3 Correct 7 ms 11972 KB Output is correct
4 Correct 8 ms 12372 KB Output is correct
5 Correct 8 ms 12152 KB Output is correct
6 Correct 8 ms 12628 KB Output is correct
7 Correct 12 ms 13980 KB Output is correct
8 Correct 8 ms 12388 KB Output is correct
9 Correct 35 ms 22620 KB Output is correct
10 Correct 8 ms 12364 KB Output is correct
11 Correct 8 ms 12364 KB Output is correct
12 Correct 42 ms 23120 KB Output is correct
13 Correct 69 ms 26276 KB Output is correct
14 Correct 58 ms 23076 KB Output is correct
15 Correct 61 ms 25792 KB Output is correct
16 Correct 65 ms 26300 KB Output is correct
17 Correct 64 ms 21300 KB Output is correct
18 Correct 69 ms 24260 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 8 ms 12472 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 8 ms 12620 KB Output is correct
7 Correct 11 ms 14016 KB Output is correct
8 Correct 7 ms 12340 KB Output is correct
9 Correct 51 ms 22584 KB Output is correct
10 Correct 8 ms 12372 KB Output is correct
11 Correct 8 ms 12364 KB Output is correct
12 Correct 40 ms 23224 KB Output is correct
13 Correct 61 ms 26380 KB Output is correct
14 Correct 60 ms 23096 KB Output is correct
15 Correct 60 ms 25836 KB Output is correct
16 Correct 62 ms 26300 KB Output is correct
17 Correct 69 ms 21280 KB Output is correct
18 Correct 64 ms 24248 KB Output is correct
19 Correct 396 ms 82544 KB Output is correct
20 Correct 428 ms 67216 KB Output is correct
21 Correct 390 ms 84360 KB Output is correct
22 Correct 419 ms 92336 KB Output is correct
23 Correct 184 ms 66128 KB Output is correct
24 Correct 444 ms 63252 KB Output is correct
25 Correct 449 ms 79532 KB Output is correct