oj.uz

Submission #960674

# Submission time Handle Problem Language Result Execution time Memory
960674 2024-04-10T22:01:27 Z dpsaveslives Senior Postmen (BOI14_postmen) C++17
100 / 100
 328 ms 71364 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 5e5+10;
vector<pair<int,int>> adj[MAXN]; //for knowing whether we visited this edge before, we save the edge index
vector<bool> visedge, vis;
vector<int> cyc;
int cur;
void dfs(int u){
    vis[u] = true; cyc.push_back(u);
    while(!adj[u].empty()){
        while(!adj[u].empty() && visedge[adj[u].back().s]){
            adj[u].pop_back();
        }
        if(adj[u].empty()){ //give up -> this one won't be added in the cycle!
            cyc.pop_back();
            return;
        }
        int v = adj[u].back().f;
        visedge[adj[u].back().s] = true;
        if(vis[v]){
            cur = v;
            cout << v << " ";
            while(cyc.back() != v){
                cout << cyc.back() << " ";
                vis[cyc.back()] = false; cyc.pop_back();
            }
            cout << "\n";
        }
        else{
            dfs(v);
        }
        if(u != cur){
            //AHHHHHH (we cannot continue here)
            return;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M;
    visedge = vector<bool>(M,false), vis = vector<bool>(N+1,false);
    for(int i = 0;i<M;++i){
        int u,v; cin >> u >> v;
        adj[u].push_back({v,i}); adj[v].push_back({u,i});
    }
    for(int i = 1;i<=N;++i){ //is this necessary? Or can we just do it in one? It is necessary! Otherwise we might get stuck
        dfs(i);
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12204 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 4 ms 12120 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 24 ms 15308 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12120 KB Output is correct
12 Correct 26 ms 15700 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12196 KB Output is correct
2 Correct 4 ms 12120 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 5 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 4 ms 12376 KB Output is correct
9 Correct 24 ms 15196 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12120 KB Output is correct
12 Correct 30 ms 15696 KB Output is correct
13 Correct 43 ms 23760 KB Output is correct
14 Correct 34 ms 16832 KB Output is correct
15 Correct 37 ms 16084 KB Output is correct
16 Correct 51 ms 23784 KB Output is correct
17 Correct 37 ms 16620 KB Output is correct
18 Correct 37 ms 18852 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 4 ms 12132 KB Output is correct
4 Correct 4 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 6 ms 12140 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 23 ms 15132 KB Output is correct
10 Correct 4 ms 12376 KB Output is correct
11 Correct 5 ms 12120 KB Output is correct
12 Correct 26 ms 15700 KB Output is correct
13 Correct 47 ms 23760 KB Output is correct
14 Correct 39 ms 16752 KB Output is correct
15 Correct 32 ms 16084 KB Output is correct
16 Correct 41 ms 23840 KB Output is correct
17 Correct 44 ms 16672 KB Output is correct
18 Correct 35 ms 18516 KB Output is correct
19 Correct 328 ms 71280 KB Output is correct
20 Correct 260 ms 36576 KB Output is correct
21 Correct 223 ms 33976 KB Output is correct
22 Correct 315 ms 71364 KB Output is correct
23 Correct 107 ms 26700 KB Output is correct
24 Correct 266 ms 35672 KB Output is correct
25 Correct 283 ms 44752 KB Output is correct