oj.uz

답안 #824883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
824883 2023-08-14T11:37:06 Z QwertyPi 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 372 ms 62952 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 11;
int ptr[MAXN];
bool used[MAXN];
int prv[MAXN];

struct edge{
	int u, e;
};

vector<edge> G[MAXN];
vector<int> ans;

bool dfs(int s, int v, bool init){
	ans.push_back(v);
	if(!init && s == v) return true;
	while(ptr[v] < G[v].size()){
		auto [u, e] = G[v][ptr[v]++];
		if(used[e]) continue; used[e] = true;
		dfs(s, u, 0);
		return true;
	}
	return false;
}

int32_t main() {
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		G[u].push_back({v, i});
		G[v].push_back({u, i});
	}

	fill(prv, prv + n + 1, -1);
	for(int i = 1; i <= n; i++){
		while(dfs(i, i, 1)){
			vector<int> V;
			for(auto v : ans){
				if(prv[v] == -1){
					prv[v] = V.size(); V.push_back(v);
				}else{
					cout << v << ' ';
					while(V.back() != v){
						prv[V.back()] = -1;
						cout << V.back() << ' ';
						V.pop_back();
					}
					cout << '\n';
				}
				ans.clear();
			}
			prv[V.back()] = -1;
		}
	}
}

Compilation message

postmen.cpp: In function 'bool dfs(int, int, bool)':
postmen.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  while(ptr[v] < G[v].size()){
      |        ~~~~~~~^~~~~~~~~~~~~
postmen.cpp:20:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |   auto [u, e] = G[v][ptr[v]++];
      |        ^
postmen.cpp:21:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |   if(used[e]) continue; used[e] = true;
      |   ^~
postmen.cpp:21:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |   if(used[e]) continue; used[e] = true;
      |                         ^~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12112 KB Output is correct
2 Correct 6 ms 11996 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12244 KB Output is correct
7 Correct 9 ms 12628 KB Output is correct
8 Correct 6 ms 12244 KB Output is correct
9 Correct 28 ms 14616 KB Output is correct
10 Correct 7 ms 12232 KB Output is correct
11 Correct 6 ms 12304 KB Output is correct
12 Correct 27 ms 15316 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12036 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12244 KB Output is correct
7 Correct 9 ms 12628 KB Output is correct
8 Correct 6 ms 12244 KB Output is correct
9 Correct 25 ms 14668 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 6 ms 12268 KB Output is correct
12 Correct 29 ms 15344 KB Output is correct
13 Correct 41 ms 22184 KB Output is correct
14 Correct 39 ms 16212 KB Output is correct
15 Correct 38 ms 16576 KB Output is correct
16 Correct 52 ms 22216 KB Output is correct
17 Correct 42 ms 16536 KB Output is correct
18 Correct 41 ms 20248 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 6 ms 12244 KB Output is correct
7 Correct 9 ms 12628 KB Output is correct
8 Correct 6 ms 12244 KB Output is correct
9 Correct 25 ms 14676 KB Output is correct
10 Correct 8 ms 12180 KB Output is correct
11 Correct 8 ms 12244 KB Output is correct
12 Correct 28 ms 15248 KB Output is correct
13 Correct 41 ms 22212 KB Output is correct
14 Correct 39 ms 16208 KB Output is correct
15 Correct 44 ms 16592 KB Output is correct
16 Correct 43 ms 22232 KB Output is correct
17 Correct 41 ms 16572 KB Output is correct
18 Correct 41 ms 20164 KB Output is correct
19 Correct 339 ms 62936 KB Output is correct
20 Correct 293 ms 33216 KB Output is correct
21 Correct 267 ms 34312 KB Output is correct
22 Correct 372 ms 62952 KB Output is correct
23 Correct 109 ms 23544 KB Output is correct
24 Correct 327 ms 34884 KB Output is correct
25 Correct 329 ms 59760 KB Output is correct