Submission #790442

#	Time	Username	Problem	Language	Result	Execution time	Memory
790442		bane	Senior Postmen (BOI14_postmen)	C++17	100 / 100	390 ms	92292 KiB

postmen

    #include<bits/stdc++.h> 
    using namespace std; 
    #define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
    #define ford(i, a, b) for(int i = (int) (b); i >= (int) (a); i--) 
    #define ii pair<int, int> 
    #define fi first
    #define se second
    #define vi vector<int> 
    #define eb emplace_back
    #define sp ' '
    #define endl '\n'
    #define int long long
    const int maxn = 5e5 + 5; 
    int n, m;
    vector<ii> g[maxn]; 
    bool used[maxn]; 
    int pt[maxn]; 
    vector<int> ans; 
    void dfs(int); 
    vector<vi> decompose(); 
    bool vs[maxn]; 
    void dfs(int u) { 
    	while(pt[u] < g[u].size()) {
    		int id = g[u][pt[u]].se, v = g[u][pt[u]].fi; 
    		if(!used[id]) { 
    			used[id] = 1; 
    			dfs(v); 
    		}
    		++pt[u]; 
    	}
    	ans.eb(u); 
    //	cout << u << endl; 
    }
    vector<vi> decompose() { 
    	stack<int> cur; 
    	vector<vi> re; 
    	for(int u: ans) { 
    		if(!vs[u]) { 
    			cur.push(u); 
    			vs[u] = 1; 
    		}
    		else { 
    			vi cyc; 
    			while(vs[u]) { 
    				cyc.eb(cur.top()); 
    				vs[cur.top()] = 0; 
    				cur.pop(); 
    			}
    			re.eb(cyc); 
    			cur.push(u); 
    			vs[u] = 1; 
    		}
    	}
    	return re; 		
    }
    signed main() { 
    	ios_base::sync_with_stdio(0); 
    	cin.tie(0); 
    	cout.tie(0); 
    	cin >> n >> m; 
    	fori(i, 1, m) { 
    		int u, v; cin >> u >> v; 
    		g[u].eb(v, i); 
    		g[v].eb(u, i); 
    	}
    	dfs(1); // since the thing is connected
    	auto t = decompose(); 
    	for(auto cyc: t) { 
    		for(int u: cyc) { 
    			cout << u << sp; 
    		}
    		cout << endl; 
    	}
    }

Compilation message (stderr)

postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:23:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |      while(pt[u] < g[u].size()) {
      |            ~~~~~~^~~~~~~~~~~~~

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