oj.uz

Submission #570415

# Submission time Handle Problem Language Result Execution time Memory
570415 2022-05-29T15:38:22 Z cheissmart Parachute rings (IOI12_rings) C++14
100 / 100
 1323 ms 78984 KB 
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7, N = 1e6 + 7;

struct Graph {
    int deg[N], cycle_cnt, cycle_sz;
    int p[N], sz[N];
    bool ok;
    void init(int n) {
        ok = true;
        for(int i = 0; i < n; i++)
            p[i] = i, sz[i] = 1;
    }
    int find(int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        assert(u != v);
        if(sz[u] > sz[v]) swap(u, v);
        p[u] = v;
        sz[v] += sz[u];
    }
    void add_edge(int u, int v) {
        deg[u]++, deg[v]++;
        if(deg[u] >= 3 || deg[v] >= 3) ok = false;
        if(find(u) == find(v)) {
            ok = false;
            cycle_cnt++;
            cycle_sz = sz[find(u)];
        } else {
            unite(u, v);
        }
    }
} G, g[4];

vi special;

int n;
V<pi> todo;
bool has4 = false;

void Init(int _n) {
    n = _n;
    G.init(n);
    for(int i = 0; i < 4; i++)
        g[i].init(n);
}
 
void add_edge(int u, int v) {
    for(int i = 0; i < 4; i++) {
        if(u != special[i] && v != special[i]) {
            g[i].add_edge(u, v);
        }
    }
}

void found4(int x) {
    has4 = true;
    special.PB(x);
    for(auto[u, v]:todo) if(u == x || v == x)
        special.PB(u ^ v ^ x);
    assert(SZ(special) == 4);
    for(auto[u, v]:todo)
        add_edge(u, v);
}

void Link(int u, int v) {
    if(!has4) {
        todo.EB(u, v);
        G.add_edge(u, v);
        if(G.deg[u] == 3) {
            found4(u);
            return;
        }
        if(G.deg[v] == 3) {
            found4(v);
            return;
        }
    } else {
        add_edge(u, v);
    }
}

int CountCritical() {
    if(!has4) {
        if(G.cycle_cnt == 0) return n;
        else if(G.cycle_cnt == 1) return G.cycle_sz;
        else return 0;
    }
    return g[0].ok + g[1].ok + g[2].ok + g[3].ok;
}

Compilation message

rings.cpp: In function 'void found4(int)':
rings.cpp:76:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for(auto[u, v]:todo) if(u == x || v == x)
      |             ^
rings.cpp:79:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto[u, v]:todo)
      |             ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 852 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 33908 KB Output is correct
2 Correct 955 ms 60332 KB Output is correct
3 Correct 1027 ms 71840 KB Output is correct
4 Correct 499 ms 64720 KB Output is correct
5 Correct 484 ms 64708 KB Output is correct
6 Correct 424 ms 63788 KB Output is correct
7 Correct 979 ms 71276 KB Output is correct
8 Correct 1176 ms 73004 KB Output is correct
9 Correct 1323 ms 78984 KB Output is correct
10 Correct 401 ms 63616 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 4 ms 1236 KB Output is correct
14 Correct 3 ms 1108 KB Output is correct
15 Correct 5 ms 1620 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 4 ms 1108 KB Output is correct
18 Correct 4 ms 1788 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 4 ms 1236 KB Output is correct
14 Correct 3 ms 1108 KB Output is correct
15 Correct 5 ms 1620 KB Output is correct
16 Correct 3 ms 1108 KB Output is correct
17 Correct 4 ms 1108 KB Output is correct
18 Correct 4 ms 1788 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 6 ms 1236 KB Output is correct
21 Correct 12 ms 3544 KB Output is correct
22 Correct 22 ms 5332 KB Output is correct
23 Correct 26 ms 6448 KB Output is correct
24 Correct 37 ms 6364 KB Output is correct
25 Correct 14 ms 6356 KB Output is correct
26 Correct 40 ms 6988 KB Output is correct
27 Correct 25 ms 6328 KB Output is correct
28 Correct 37 ms 6748 KB Output is correct
29 Correct 27 ms 7068 KB Output is correct
30 Correct 29 ms 6848 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 708 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 184 ms 33908 KB Output is correct
12 Correct 955 ms 60332 KB Output is correct
13 Correct 1027 ms 71840 KB Output is correct
14 Correct 499 ms 64720 KB Output is correct
15 Correct 484 ms 64708 KB Output is correct
16 Correct 424 ms 63788 KB Output is correct
17 Correct 979 ms 71276 KB Output is correct
18 Correct 1176 ms 73004 KB Output is correct
19 Correct 1323 ms 78984 KB Output is correct
20 Correct 401 ms 63616 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 4 ms 1364 KB Output is correct
23 Correct 4 ms 1236 KB Output is correct
24 Correct 3 ms 1108 KB Output is correct
25 Correct 5 ms 1620 KB Output is correct
26 Correct 3 ms 1108 KB Output is correct
27 Correct 4 ms 1108 KB Output is correct
28 Correct 4 ms 1788 KB Output is correct
29 Correct 3 ms 1108 KB Output is correct
30 Correct 6 ms 1236 KB Output is correct
31 Correct 12 ms 3544 KB Output is correct
32 Correct 22 ms 5332 KB Output is correct
33 Correct 26 ms 6448 KB Output is correct
34 Correct 37 ms 6364 KB Output is correct
35 Correct 14 ms 6356 KB Output is correct
36 Correct 40 ms 6988 KB Output is correct
37 Correct 25 ms 6328 KB Output is correct
38 Correct 37 ms 6748 KB Output is correct
39 Correct 27 ms 7068 KB Output is correct
40 Correct 29 ms 6848 KB Output is correct
41 Correct 139 ms 29392 KB Output is correct
42 Correct 526 ms 61304 KB Output is correct
43 Correct 243 ms 56640 KB Output is correct
44 Correct 713 ms 66856 KB Output is correct
45 Correct 687 ms 68528 KB Output is correct
46 Correct 368 ms 54700 KB Output is correct
47 Correct 406 ms 55600 KB Output is correct
48 Correct 472 ms 67036 KB Output is correct
49 Correct 367 ms 61780 KB Output is correct
50 Correct 392 ms 60724 KB Output is correct
51 Correct 282 ms 51276 KB Output is correct
52 Correct 626 ms 54372 KB Output is correct
53 Correct 507 ms 66248 KB Output is correct
54 Correct 1065 ms 63116 KB Output is correct
55 Correct 1097 ms 64516 KB Output is correct