Submission #1262428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262428		ZeroCool	Senior Postmen (BOI14_postmen)	C++20	55 / 100	553 ms	129020 KiB

postmen

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;;
#define ll long long
#define ar array

template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// #define int long long
#define all(v) v.begin(), v.end()
#define ld long double

const int N = 5e5 + 20;
const int M = 2;
const int LOG = 20;
const ll INF = 1e14;
int MOD = 998244353;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

int n, m;
set<int> g[N];

vector<int> euler;

void dfs(int x){
	while(g[x].size()){
		int u = *g[x].begin();
		g[x].erase(g[x].begin());
		g[u].erase(x);
		dfs(u);
	}
	euler.push_back(x);
}

void orz(){
	cin>>n>>m;
	for(int i = 0;i < m;i++){
		int a, b;
		cin>>a>>b;
		--a, --b;
		g[a].insert(b);
		g[b].insert(a);
	}
	dfs(0);
	bool vis[n] = {0};
	vector<int> v;
	for(auto u: euler){
		if(vis[u]){
			cout<<1 + u<<" ";
			while(v.size() && v.back() != u){
				cout<<v.back() + 1<<" ";
				vis[v.back()] = 0;
				v.pop_back();
			}
			cout<<'\n';
		}else v.push_back(u), vis[u] = 1;
	}
}

signed main() { 		
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while (t--)orz();
}

//I am stupid :D

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