Submission #1262393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262393		ZeroCool	Senior Postmen (BOI14_postmen)	C++20	0 / 100	1096 ms	20852 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 = 4e5 + 20;
const int M = 2;
const int LOG = 20;
const ll INF = 1e17;
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;};

bool vis[N];
set<int> g[N];

vector<int> P;
vector<int> Q;
set<int> s;
void dfs(int x,int p,int st){
	P.push_back(x);
	vis[x] = 1;
	s.insert(x);
	//cout<<1 + x<<' ';
	for(auto u: g[x]){
		if(u == p)continue;
		if(u == st){
			Q = P;
			return;
		}
		if(!vis[u])dfs(u, x, st);
	}

	P.pop_back();
}

void orz(){
	int n, m;
	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);
	}
	for(int i = 0;i < n;i++){
		while(g[i].size() > 0){
			P.clear();
			Q.clear();
			s.clear();
			dfs(i, i, i);
			for(auto u: Q)cout<<u + 1<<" ";
			cout<<'\n';
			int y = Q.back();
			for(auto x: Q){
				g[y].erase(x);
				g[x].erase(y);
				y = x;
			}
			for(auto i: s)vis[i] = 0;
		}
	}
}

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

//I am stupid :D

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