Submission #790404

#	Time	Username	Problem	Language	Result	Execution time	Memory
790404		bane	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1091 ms	24112 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);
        vector<vector<pair<int,int>>>adj(nax);
        vector<int>pracka;
		inline int readint(){
			int ret=0;
			for(char c;;){
				c=getchar_unlocked();
				if('0'<=c and c<='9')
					ret=ret*10+(c&15);
				else
					return ret;
			}
		}
		vector<char> digits;
		inline void printint(int x){
			do{
				digits.push_back(x%10|48);
				x/=10;
			}while(x);
			while(not digits.empty())
				putchar(digits.back()), digits.pop_back();
		}
        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 = readint();
			int m = readint();
        	for (int i = 0; i < m; i++){
        		int a,b;
				a = readint();
				b = readint();
        		--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]){
					printint(j + 1);
					putchar(' ');
				}
				putchar('\n');
        	}
        }
         
        int main(){
        	solve();
        	return 0;
        }

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