Submission #790391

#	Time	Username	Problem	Language	Result	Execution time	Memory
790391		bane	Senior Postmen (BOI14_postmen)	C++17	0 / 100	6 ms	13908 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;
    		scanf("%d %d", &n, &m);
        	vector<pair<int,int>>edges;
			for (int i = 0; i < m; i++){
        		int a,b;
        		scanf("%d %d", &a, &b);
        		--a,--b;
				if (a > b)swap(a,b);
				edges.pb(mp(a,b));
        	}
			sort(edges.begin(), edges.end());
			for (int i = 0; i < m; i++){
				int a = edges[i].fr;
				int b = edges[i].sc;
				if (i && edges[i-1].fr == a && edges[i-1].sc == b)continue;
				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]);
					int inloop = 0;
        			while(c.top() != pracka[r]){
						inloop++;
						assert(inloop <= m);
        				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])printf("%d ", j + 1);
    			printf("\n");
        	}
        }
         
        int main(){
        	solve();
        	return 0;
        }

Compilation message (stderr)

postmen.cpp: In function 'void solve()':
postmen.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |       scanf("%d %d", &n, &m);
      |       ~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp:48:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |           scanf("%d %d", &a, &b);
      |           ~~~~~^~~~~~~~~~~~~~~~~

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