oj.uz

Submission #1042683

# Submission time Handle Problem Language Result Execution time Memory
1042683 2024-08-03T09:39:32 Z Ausp3x Parachute rings (IOI12_rings) C++17
0 / 100
 674 ms 84008 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;

    UnionFind(int n): 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];
        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;
vector<int> edg_cnts;
vector<vector<int>> adjl;
UnionFind uf(1000000);

void Init(int n) {
    N = n;
    edg_cnts.resize(n);
    adjl.resize(n);

    return;
}

void Link(int a, int b) {
    edg_cnts[a]++;
    edg_cnts[b]++;
    adjl[a].pb(b);
    adjl[b].pb(a);
    E = max({E, edg_cnts[a], edg_cnts[b]});
    uf.uniteSets(a, b);

    return;
}

int CountCritical() {
    if (E <= 2) {
        map<int, int> cycle_sizes;
        for (int i = 0; i < N; i++) {
            int ii = uf.findSet(i);
            if (uf.node_size[ii] == uf.edge_size[ii])
                cycle_sizes[ii] = uf.node_size[ii];
        } 
        
        if (cycle_sizes.size() == 0)
            return N;

        if (cycle_sizes.size() == 1)
            return cycle_sizes[0];

        return 0;
    }

    int greater_than_two_edges = 0;
    for (int i = 0; i < N; i++)
        if (edg_cnts[i] > 2)
            greater_than_two_edges++;

    
    for (int i = 0; i < N; i++) {
        if (edg_cnts[i] > 2) {
            int cur = 1;
            for (int j : adjl[i])
                if (edg_cnts[j] == 3)
                    cur++;
            
            if (cur < greater_than_two_edges)
                return 0;

            if (cur == greater_than_two_edges)
                return 1;
        }
    }

    return -1;
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
    }

    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 |     UnionFind(int n): n(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:30:22: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   30 |     int findSet(int v) {
      |                      ^
rings.cpp:30:22: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:30:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:30:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:38:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   38 |     bool isSameSet(int a, int b) {
      |                                ^
rings.cpp:38:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:38:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:38:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:42:32: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   42 |     void uniteSets(int a, int b) {
      |                                ^
rings.cpp:42:32: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:42:32: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:42:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:61:21: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   61 |     void debugPrint() {
      |                     ^
rings.cpp:61:21: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:61:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:61:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:85:16: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   85 | void Init(int n) {
      |                ^
rings.cpp:85:16: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:85:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:85:16: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:93:23: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   93 | void Link(int a, int b) {
      |                       ^
rings.cpp:93:23: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:93:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:93:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
rings.cpp:104:19: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  104 | int CountCritical() {
      |                   ^
rings.cpp:104:19: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
rings.cpp:104:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
rings.cpp:104:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 6 ms 12444 KB Output is correct
4 Incorrect 6 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 49616 KB Output is correct
2 Correct 504 ms 69688 KB Output is correct
3 Correct 598 ms 79384 KB Output is correct
4 Incorrect 674 ms 84008 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 6 ms 12444 KB Output is correct
4 Incorrect 6 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 6 ms 12444 KB Output is correct
4 Incorrect 6 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 5 ms 12380 KB Output is correct
3 Correct 6 ms 12444 KB Output is correct
4 Incorrect 6 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -