Submission #824879

#	Time	Username	Problem	Language	Result	Execution time	Memory
824879		QwertyPi	Senior Postmen (BOI14_postmen)	C++14	55 / 100	510 ms	69700 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 11;
int ptr[MAXN];
bool used[MAXN];
int prv[MAXN];
vector<pair<int, int>> 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() {
	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});
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < G[i].size(); j++){
			if(G[i][j].first == 1) swap(G[i][j], G[i].back());
		}
	}

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45