Submission #824883

#	Time	Username	Problem	Language	Result	Execution time	Memory
824883		QwertyPi	Senior Postmen (BOI14_postmen)	C++14	100 / 100	372 ms	62952 KiB

postmen

#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 (stderr)

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 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45