Submission #1170518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170518		ZeroCool	Senior Postmen (BOI14_postmen)	C++20	100 / 100	256 ms	85276 KiB

postmen

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

const int N = 1e6 + 20;
const int K = 469;
const int LOG = 26;
const int INF = 1e12;	
int MOD = 998244353;

int n, m;
vector<ar<int,2>> g[N];

vector<int> ord;
bool vis[N];
void dfs(int x){
	while(g[x].size()){
		auto [u, i] = g[x].back();
		g[x].pop_back();
		if(!vis[i]){
			vis[i] = 1;
			dfs(u);
		}
	}
	ord.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].push_back({b, i});
		g[b].push_back({a, i});
	}
	dfs(0);
	stack<int> s;
	bool in[n] = {0};
	for(auto u: ord){
		if(in[u]){
			cout<<u + 1<<" ";
			while(s.top() != u){
				in[s.top()] = 0;
				cout<<s.top() + 1<<" ";
				s.pop();
			}
			s.pop();
			in[u] = 0;
			cout<<'\n';
		}
		s.push(u);
		in[u] = 1;
	}
}	
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	//cin>>t;
	t = 1;
	while(t--)orz();
}
	

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