oj.uz

Submission #1043598

# Submission time Handle Problem Language Result Execution time Memory
1043598 2024-08-04T11:51:02 Z Ausp3x Parachute rings (IOI12_rings) C++17
100 / 100
 1334 ms 146772 KB 
// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long    lng;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

struct UnionFind {
    int n;
    vector<int> link, node_size, edge_size;

    void init(int n) {
        this->n = n;
        link.resize(n + 1);
        iota(link.begin(), link.end(), 0);
        node_size.resize(n + 1, 1);
        edge_size.resize(n + 1);
    }

    int findSet(int v) {
        if (v == link[v]) {
            return link[v];
        }
            
        return link[v] = findSet(link[v]);
    }

    bool isSameSet(int a, int b) {
        return findSet(a) == findSet(b);
    }

    void uniteSets(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (node_size[a] < node_size[b]) {
            swap(a, b);
        }

        if (a == b) {
            edge_size[a]++;
            return;
        }

        node_size[a] += node_size[b];
        edge_size[a] += edge_size[b] + 1;
        link[b] = a;

        return;
    }

    void debugPrint() {
        cout << n << endl;
        cout << "link:" << endl;
        for (int x : link)
            cout << x << ' ';
        cout << endl;
        cout << "node_size:" << endl;
        for (int x : node_size)
            cout << x << ' ';
        cout << endl;
        cout << "edge_size:" << endl;
        for (int x : edge_size)
            cout << x << ' ';
        cout << endl;

        return;
    }
};

int N, E = 0;
int simple_cycle_size = -1;
vector<int> edg_cnts;
vector<vector<int>> adjl;
UnionFind uf_all;

vector<vector<int>> cands_edg_cnts(4);
vector<UnionFind> uf_cands(4);

void Init(int n) {
    N = n;
    edg_cnts.resize(n);
    adjl.resize(n);
    uf_all.init(n);
    for (int i = 0; i < 4; i++)
        cands_edg_cnts[i].resize(n);
    for (int i = 0; i < 4; i++)
        uf_cands[i].init(n);

    return;
}

bool is_impossible = false;
vector<bool> is_pos_cands(4, true);
vector<int> idxs(4);

void Link(int a, int b) {
    if (edg_cnts[a] < edg_cnts[b])
        swap(a, b);

    edg_cnts[a]++;
    edg_cnts[b]++;
    adjl[a].pb(b);
    adjl[b].pb(a);

    if (edg_cnts[a] > E && edg_cnts[a] == 3) {
        E = edg_cnts[a];
        uf_all.uniteSets(a, b);

        assert(adjl[a].size() == 3);

        idxs[0] = a;
        for (int i = 0; i < 3; i++) 
            idxs[i + 1] = adjl[a][i];

        // for (int x : idxs)
        //     cout << x << ' ';
        // cout << endl;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < N; j++) {
                if (j == idxs[i])
                    continue;
                
                for (int k : adjl[j]) {
                    if (k == idxs[i])
                        continue;

                    if (k < j)
                        continue;

                    cands_edg_cnts[i][j]++;
                    cands_edg_cnts[i][k]++;
                    if (cands_edg_cnts[i][j] >= 3 || cands_edg_cnts[i][k] >= 3)
                        is_pos_cands[i] = false;

                    if (uf_cands[i].findSet(j) == uf_cands[i].findSet(k))
                        is_pos_cands[i] = false;
                    uf_cands[i].uniteSets(j, k);
                }
            }
        }

        // for (int i = 0; i < 4; i++) {
        //     for (int j = 0; j < N; j++)
        //         cout << cands_edg_cnts[i][j] << ' ';
        //     cout << endl;
        // }

        bool has_candidates = false;
        for (int i = 0; i < 4; i++)
            has_candidates |= is_pos_cands[i];

        if (!has_candidates)
            is_impossible = true;
        
        // cout << is_impossible << endl;

        return;
    }

    E = max(E, edg_cnts[a]);

    if (E == 2 && uf_all.findSet(a) == uf_all.findSet(b)) {
        uf_all.uniteSets(a, b);
        
        if (simple_cycle_size != -1) {
            is_impossible = true;
            return;
        }

        simple_cycle_size = uf_all.node_size[uf_all.findSet(a)];
        return;
    }

    uf_all.uniteSets(a, b);

    if (E >= 3) {
        for (int i = 0; i < 4; i++) {
            if (idxs[i] == a || idxs[i] == b)
                continue;

            cands_edg_cnts[i][a]++;
            cands_edg_cnts[i][b]++;
            if (cands_edg_cnts[i][a] >= 3 || cands_edg_cnts[i][b] >= 3)
                is_pos_cands[i] = false;

            if (uf_cands[i].findSet(a) == uf_cands[i].findSet(b))
                is_pos_cands[i] = false; 
            uf_cands[i].uniteSets(a, b);
        }

        bool has_candidates = false;
        for (int i = 0; i < 4; i++)
            has_candidates |= is_pos_cands[i];

        if (!has_candidates)
            is_impossible = true;

        return;
    }

    return;
}

int CountCritical() {
    if (is_impossible)
        return 0;

    if (E <= 1)
        return N;
    
    if (E == 2)
        return (simple_cycle_size == -1 ? N : simple_cycle_size);

    return accumulate(is_pos_cands.begin(), is_pos_cands.end(), 0);
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while (t--) {
        int n, l;
        cin >> n >> l;
        Init(n);
        while (l--) {
            int a;
            cin >> a;

            if (a == -1) {
                cout << CountCritical() << endl;
                continue;
            }

            int b;
            cin >> b;
            Link(a, b);
        }
    }

    return 0;
}
#endif

Compilation message

rings.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
rings.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
rings.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
rings.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
rings.cpp:23:20: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   23 |     void init(int n) {
      |                    ^
rings.cpp:23:20: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:23:20: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:23:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:31:22: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   31 |     int findSet(int v) {
      |                      ^
rings.cpp:31:22: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:31:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:31:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:39:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   39 |     bool isSameSet(int a, int b) {
      |                                ^
rings.cpp:39:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:39:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:39:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:43:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   43 |     void uniteSets(int a, int b) {
      |                                ^
rings.cpp:43:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:43:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:43:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:62:21: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   62 |     void debugPrint() {
      |                     ^
rings.cpp:62:21: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:62:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:62:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:90:16: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   90 | void Init(int n) {
      |                ^
rings.cpp:90:16: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:90:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:90:16: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:107:23: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  107 | void Link(int a, int b) {
      |                       ^
rings.cpp:107:23: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:107:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:107:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:216:19: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  216 | int CountCritical() {
      |                   ^
rings.cpp:216:19: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:216:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:216:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 988 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 836 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 76444 KB Output is correct
2 Correct 1076 ms 117584 KB Output is correct
3 Correct 1334 ms 142116 KB Output is correct
4 Correct 543 ms 146772 KB Output is correct
5 Correct 543 ms 146772 KB Output is correct
6 Correct 545 ms 144756 KB Output is correct
7 Correct 1244 ms 141024 KB Output is correct
8 Correct 1155 ms 137300 KB Output is correct
9 Correct 1155 ms 146712 KB Output is correct
10 Correct 349 ms 144208 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 988 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 836 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 5 ms 1884 KB Output is correct
13 Correct 4 ms 1884 KB Output is correct
14 Correct 3 ms 1628 KB Output is correct
15 Correct 3 ms 2652 KB Output is correct
16 Correct 2 ms 1884 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 5 ms 2908 KB Output is correct
19 Correct 3 ms 1884 KB Output is correct
20 Correct 4 ms 1892 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 988 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 836 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 5 ms 1884 KB Output is correct
13 Correct 4 ms 1884 KB Output is correct
14 Correct 3 ms 1628 KB Output is correct
15 Correct 3 ms 2652 KB Output is correct
16 Correct 2 ms 1884 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 5 ms 2908 KB Output is correct
19 Correct 3 ms 1884 KB Output is correct
20 Correct 4 ms 1892 KB Output is correct
21 Correct 12 ms 6748 KB Output is correct
22 Correct 21 ms 10844 KB Output is correct
23 Correct 20 ms 13404 KB Output is correct
24 Correct 31 ms 12124 KB Output is correct
25 Correct 12 ms 10840 KB Output is correct
26 Correct 32 ms 12912 KB Output is correct
27 Correct 23 ms 12628 KB Output is correct
28 Correct 39 ms 13280 KB Output is correct
29 Correct 25 ms 12628 KB Output is correct
30 Correct 34 ms 14604 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 988 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 836 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct
11 Correct 191 ms 76444 KB Output is correct
12 Correct 1076 ms 117584 KB Output is correct
13 Correct 1334 ms 142116 KB Output is correct
14 Correct 543 ms 146772 KB Output is correct
15 Correct 543 ms 146772 KB Output is correct
16 Correct 545 ms 144756 KB Output is correct
17 Correct 1244 ms 141024 KB Output is correct
18 Correct 1155 ms 137300 KB Output is correct
19 Correct 1155 ms 146712 KB Output is correct
20 Correct 349 ms 144208 KB Output is correct
21 Correct 3 ms 1112 KB Output is correct
22 Correct 5 ms 1884 KB Output is correct
23 Correct 4 ms 1884 KB Output is correct
24 Correct 3 ms 1628 KB Output is correct
25 Correct 3 ms 2652 KB Output is correct
26 Correct 2 ms 1884 KB Output is correct
27 Correct 3 ms 1884 KB Output is correct
28 Correct 5 ms 2908 KB Output is correct
29 Correct 3 ms 1884 KB Output is correct
30 Correct 4 ms 1892 KB Output is correct
31 Correct 12 ms 6748 KB Output is correct
32 Correct 21 ms 10844 KB Output is correct
33 Correct 20 ms 13404 KB Output is correct
34 Correct 31 ms 12124 KB Output is correct
35 Correct 12 ms 10840 KB Output is correct
36 Correct 32 ms 12912 KB Output is correct
37 Correct 23 ms 12628 KB Output is correct
38 Correct 39 ms 13280 KB Output is correct
39 Correct 25 ms 12628 KB Output is correct
40 Correct 34 ms 14604 KB Output is correct
41 Correct 123 ms 63572 KB Output is correct
42 Correct 461 ms 108476 KB Output is correct
43 Correct 190 ms 101456 KB Output is correct
44 Correct 963 ms 134588 KB Output is correct
45 Correct 859 ms 131176 KB Output is correct
46 Correct 311 ms 121168 KB Output is correct
47 Correct 436 ms 123472 KB Output is correct
48 Correct 527 ms 124956 KB Output is correct
49 Correct 371 ms 138068 KB Output is correct
50 Correct 359 ms 136260 KB Output is correct
51 Correct 268 ms 89732 KB Output is correct
52 Correct 744 ms 108368 KB Output is correct
53 Correct 557 ms 125264 KB Output is correct
54 Correct 1048 ms 118868 KB Output is correct
55 Correct 1285 ms 129616 KB Output is correct