oj.uz

Submission #1027952

# Submission time Handle Problem Language Result Execution time Memory
1027952 2024-07-19T11:54:35 Z anarch_y Senior Postmen (BOI14_postmen) C++17
100 / 100
 308 ms 65344 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
 
const int maxn = 500001;
vector<pair<int, int>> adj[maxn];
vector<bool> seen;
vector<int> path;
 
void dfs(int s){
    while(!adj[s].empty()){
        auto [u, id] = adj[s].back();
        adj[s].pop_back();
        if(seen[id]) continue;
        seen[id] = true;
        dfs(u);
    }
    path.pb(s);
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int n, m; cin >> n >> m;
    seen.resize(m+1);
    for(int i=1; i<=m; i++){
        int a, b; cin >> a >> b;
        adj[a].pb({b, i}); adj[b].pb({a, i});
    }
    dfs(1);
    reverse(all(path));
    int v[n+1] = {};
    vector<int> w;
    for(auto s: path){
        if(v[s]){
            cout << s << ' ';
            while(w.back() != s){
                auto t = w.back();
                w.pop_back();
                v[t] = 0;
                cout << t << ' ';
            }
            cout << "\n";
        }
        else{
            v[s] = 1;
            w.pb(s);
        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 3 ms 12120 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 4 ms 12632 KB Output is correct
7 Correct 6 ms 13404 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 34 ms 20392 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 27 ms 20692 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 2 ms 12192 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 5 ms 12376 KB Output is correct
7 Correct 7 ms 13496 KB Output is correct
8 Correct 3 ms 12376 KB Output is correct
9 Correct 25 ms 19668 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 45 ms 20172 KB Output is correct
13 Correct 56 ms 22396 KB Output is correct
14 Correct 47 ms 19668 KB Output is correct
15 Correct 34 ms 21704 KB Output is correct
16 Correct 44 ms 22360 KB Output is correct
17 Correct 31 ms 17360 KB Output is correct
18 Correct 35 ms 20500 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12124 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 8 ms 13404 KB Output is correct
8 Correct 3 ms 12376 KB Output is correct
9 Correct 30 ms 20540 KB Output is correct
10 Correct 6 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 28 ms 20696 KB Output is correct
13 Correct 38 ms 22352 KB Output is correct
14 Correct 52 ms 19504 KB Output is correct
15 Correct 36 ms 21456 KB Output is correct
16 Correct 39 ms 21324 KB Output is correct
17 Correct 36 ms 17364 KB Output is correct
18 Correct 55 ms 20540 KB Output is correct
19 Correct 262 ms 62608 KB Output is correct
20 Correct 231 ms 48924 KB Output is correct
21 Correct 188 ms 58808 KB Output is correct
22 Correct 308 ms 65344 KB Output is correct
23 Correct 127 ms 52308 KB Output is correct
24 Correct 217 ms 36888 KB Output is correct
25 Correct 268 ms 56688 KB Output is correct