Submission #530874

#	Time	Username	Problem	Language	Result	Execution time	Memory
530874		hohohaha	Senior Postmen (BOI14_postmen)	C++14	100 / 100	449 ms	92336 KiB

postmen

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

Compilation message (stderr)

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

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