oj.uz

Submission #399018

# Submission time Handle Problem Language Result Execution time Memory
399018 2021-05-05T04:12:01 Z lyc Senior Postmen (BOI14_postmen) C++14
100 / 100
 274 ms 66360 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
typedef pair<int,int> ii;

const int mxN = 5e5+5;
const int mxM = 5e5+5;

int N, M;
struct Edge { int v, i, n; } el[2*mxM];
int al[mxN];
bool vis[mxN];
bool used[mxM];

vector<int> cyc;
void dfs(int u) {
    if (vis[u]) {
        int v;
        do {
            v = cyc.back();
            cout << v << ' ';
            cyc.pop_back();
            vis[v] = 0;
        } while (v != u);
        cout << '\n';
    }

    cyc.push_back(u);
    vis[u] = 1;
    while (al[u] > 0) {
        Edge e = el[al[u]];
        al[u] = e.n;
        if (!used[e.i]) {
            used[e.i] = 1;
            dfs(e.v);
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N >> M;
    FOR(i,1,M){
        int U, V; cin >> U >> V;
        el[2*i-1] = (Edge){V,i,al[U]};
        el[2*i] = (Edge){U,i,al[V]};
        al[U] = 2*i-1;
        al[V] = 2*i;
    }

    FOR(i,1,N){
        dfs(i);
        while (SZ(cyc)) {
            vis[cyc.back()] = 0;
            cyc.pop_back();
        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 34 ms 10820 KB Output is correct
10 Correct 2 ms 440 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 38 ms 11000 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 6 ms 1868 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 34 ms 10944 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 37 ms 10988 KB Output is correct
13 Correct 42 ms 12116 KB Output is correct
14 Correct 36 ms 3660 KB Output is correct
15 Correct 45 ms 11300 KB Output is correct
16 Correct 43 ms 13292 KB Output is correct
17 Correct 40 ms 5332 KB Output is correct
18 Correct 44 ms 10904 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 6 ms 1892 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 36 ms 10824 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 37 ms 10952 KB Output is correct
13 Correct 43 ms 12168 KB Output is correct
14 Correct 36 ms 3652 KB Output is correct
15 Correct 41 ms 11408 KB Output is correct
16 Correct 44 ms 13272 KB Output is correct
17 Correct 44 ms 5252 KB Output is correct
18 Correct 42 ms 10960 KB Output is correct
19 Correct 266 ms 66268 KB Output is correct
20 Correct 222 ms 24388 KB Output is correct
21 Correct 244 ms 60996 KB Output is correct
22 Correct 274 ms 66360 KB Output is correct
23 Correct 175 ms 57152 KB Output is correct
24 Correct 269 ms 27324 KB Output is correct
25 Correct 269 ms 54216 KB Output is correct