Submission #824864

#	Time	Username	Problem	Language	Result	Execution time	Memory
824864		QwertyPi	Senior Postmen (BOI14_postmen)	C++14	0 / 100	48 ms	20460 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;

void dfs(int v){
	ans.push_back(v);
	while(ptr[v] < G[v].size()){
		auto [u, e] = G[v][ptr[v]++];
		if(used[e]) continue; used[e] = true;
		dfs(u);
	}
}

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());
		}
	}
	dfs(1);
	fill(prv, prv + n + 1, -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';
		}
	}
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:13: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]
   13 |  while(ptr[v] < G[v].size()){
      |        ~~~~~~~^~~~~~~~~~~~~
postmen.cpp:14:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |   auto [u, e] = G[v][ptr[v]++];
      |        ^
postmen.cpp:15:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |   if(used[e]) continue; used[e] = true;
      |   ^~
postmen.cpp:15:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |   if(used[e]) continue; used[e] = true;
      |                         ^~~~
postmen.cpp: In function 'int32_t main()':
postmen.cpp:28: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]
   28 |   for(int j = 0; j < G[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~

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