Submission #558193

#	Time	Username	Problem	Language	Result	Execution time	Memory
558193		Shelter	Senior Postmen (BOI14_postmen)	C++17	100 / 100	446 ms	92232 KiB

postmen

#include<bits/stdc++.h> 
using namespace std; 
#define ii pair<int, int> 
#define vi vector<int> 
#define F first
#define S second
#define endl '\n'
#define int long long
const int maxn = 5e5 + 5; 
int n, m, pt[maxn];
vector<ii> g[maxn]; 
bool used[maxn], vs[maxn]; 
vector<int> ans; 
void hier(int u) { 
	while(pt[u] < g[u].size()) {
		int id = g[u][pt[u]].S, v = g[u][pt[u]].F; 
		if(!used[id]) { 
			used[id] = 1; 
			hier(v); 
		}
		++pt[u]; 
	}
	ans.emplace_back(u); 
}
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.emplace_back(cur.top()); 
				vs[cur.top()] = 0; 
				cur.pop(); 
			}
			re.emplace_back(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; 
	for(int i = 1; i <= m; i++) { 
		int u, v; cin >> u >> v; 
		g[u].emplace_back(v, i); 
		g[v].emplace_back(u, i); 
	}
	hier(1);
	auto t = decompose(); 
	for(auto cyc: t) { 
		for(int u: cyc) { 
			cout << u << ' '; 
		}
		cout << endl; 
	}
}

Compilation message (stderr)

postmen.cpp: In function 'void hier(long long int)':
postmen.cpp:15: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]
   15 |  while(pt[u] < g[u].size()) {
      |        ~~~~~~^~~~~~~~~~~~~

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