Submission #790294

#	Time	Username	Problem	Language	Result	Execution time	Memory
790294		bane	Senior Postmen (BOI14_postmen)	C++17	0 / 100	40 ms	61192 KiB

postmen

    #include<bits/stdc++.h>
    using namespace std;
     
    #ifdef LOCAL
    #include "algo/debug.h"
    #else
    #define debug(...) 42
    #endif
     
    #define fr first
    #define sc second 
    #define mp make_pair 
    #define pb push_back 
    #define pf push_front
    #define all(x) x.begin(),x.end()
    #define rall(x) x.rbegin(), x.rend()
     
     
    using ll = long long;
    using ull = unsigned long long;
    using str = string;
    using pii = pair<int,int>;
    using pll = pair<long long, long long>;
     
    const int nax = 500'001;
    vector<int>flag(nax);
    unordered_set<int>adj[nax];
    vector<int>pracka;
    void Euler(int v){
    	while(!adj[v].empty()){
    		int x = *adj[v].begin();
    		adj[v].erase(adj[v].begin());
    		adj[x].erase(v);
    		Euler(x);
    	}
    	pracka.pb(v);
    }
     
    void solve(){
    	int n, m;
    	cin >> n >> m;
    	for (int i = 0; i < m; i++){
    		int a,b;
    		cin >> a >> b;
    		--a,--b;
    		adj[a].insert(b);
    		adj[b].insert(a);
    	}
    	Euler(0);
    	int r = -1;
    	vector<vector<int>>cycles;
    	vector<int>visited(n + 1);
    	stack<int>c;
    	while(r < (int)pracka.size()){
    		++r;
    		if (visited[pracka[r]]){
    			cycles.push_back(vector<int>());
    			cycles.back().push_back(pracka[r]);
    			while(c.top() != pracka[r]){
    				visited[c.top()] = 0;
    				cycles.back().push_back(c.top());
    				c.pop();
    			}
    		}else{
    			c.push(pracka[r]);
    			visited[pracka[r]] = 1;
    		}
    	}
    	for (int i = 0; i < (int)cycles.size() - 1; i++){
    		for (int j : cycles[i])cout << ++j << " ";
    		cout << '\n';
    	}
    }
     
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	solve();
    	return 0;
    }

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