oj.uz

Submission #790442

# Submission time Handle Problem Language Result Execution time Memory
790442 2023-07-22T16:39:09 Z bane Senior Postmen (BOI14_postmen) C++17
100 / 100
 390 ms 92292 KB 
    #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

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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 12372 KB Output is correct
5 Correct 5 ms 12216 KB Output is correct
6 Correct 6 ms 12628 KB Output is correct
7 Correct 9 ms 13928 KB Output is correct
8 Correct 6 ms 12380 KB Output is correct
9 Correct 29 ms 22536 KB Output is correct
10 Correct 6 ms 12372 KB Output is correct
11 Correct 7 ms 12372 KB Output is correct
12 Correct 33 ms 23112 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12372 KB Output is correct
5 Correct 5 ms 12116 KB Output is correct
6 Correct 6 ms 12628 KB Output is correct
7 Correct 11 ms 14036 KB Output is correct
8 Correct 5 ms 12372 KB Output is correct
9 Correct 31 ms 22528 KB Output is correct
10 Correct 6 ms 12372 KB Output is correct
11 Correct 6 ms 12372 KB Output is correct
12 Correct 32 ms 23100 KB Output is correct
13 Correct 47 ms 26232 KB Output is correct
14 Correct 58 ms 23124 KB Output is correct
15 Correct 45 ms 25788 KB Output is correct
16 Correct 47 ms 27408 KB Output is correct
17 Correct 49 ms 22276 KB Output is correct
18 Correct 48 ms 25276 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 12372 KB Output is correct
5 Correct 5 ms 12116 KB Output is correct
6 Correct 6 ms 12628 KB Output is correct
7 Correct 9 ms 13916 KB Output is correct
8 Correct 5 ms 12372 KB Output is correct
9 Correct 30 ms 22576 KB Output is correct
10 Correct 6 ms 12372 KB Output is correct
11 Correct 6 ms 12404 KB Output is correct
12 Correct 33 ms 23148 KB Output is correct
13 Correct 49 ms 26248 KB Output is correct
14 Correct 51 ms 23060 KB Output is correct
15 Correct 45 ms 25812 KB Output is correct
16 Correct 47 ms 27380 KB Output is correct
17 Correct 49 ms 22336 KB Output is correct
18 Correct 49 ms 25360 KB Output is correct
19 Correct 318 ms 89004 KB Output is correct
20 Correct 334 ms 73644 KB Output is correct
21 Correct 334 ms 84256 KB Output is correct
22 Correct 341 ms 92292 KB Output is correct
23 Correct 127 ms 66136 KB Output is correct
24 Correct 390 ms 63304 KB Output is correct
25 Correct 347 ms 79532 KB Output is correct