Submission #530871

#	Time	Username	Problem	Language	Result	Execution time	Memory
530871		hohohaha	Senior Postmen (BOI14_postmen)	C++14	55 / 100	564 ms	104700 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;
multiset<int> g[maxn]; 
vector<int> ans; 
void dfs(int); 
vector<vi> decompose(); 
bool vs[maxn]; 
void dfs(int u) { 
	while(g[u].size()) { 
		int v = *begin(g[u]); 
		g[u].erase(g[u].find(v)); 
		g[v].erase(g[v].find(u)); 
		dfs(v); 
	}
	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].insert(v); 
		g[v].insert(u); 
	}
	dfs(1); // since the thing is connected
	auto t = decompose(); 
	for(auto cyc: t) { 
		for(int u: cyc) { 
			cout << u << sp; 
		}
		cout << endl; 
	}
}

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