Submission #790358

#	Time	Username	Problem	Language	Result	Execution time	Memory
790358		bane	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1091 ms	22352 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()
     
	#pragma GCC target("avx2")
	#pragma GCC optimize("O3")
	#pragma GCC optimize("Ofast,unroll-loops")
     
    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);
    vector<vector<pair<int,int>>>adj(nax);
    vector<int>pracka;
    void Euler(int v){
    	for (pii& x : adj[v]){
    		if (flag[x.sc])continue;
    		flag[x.sc] = 1;
    		Euler(x.fr);
    	}
    	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].pb({b,i});
    		adj[b].pb({a,i});
    	}
    	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);
		cout.tie(0);
    	solve();
    	return 0;
    }

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