oj.uz

Submission #1046993

# Submission time Handle Problem Language Result Execution time Memory
1046993 2024-08-07T07:24:58 Z onbert Parachute rings (IOI12_rings) C++17
0 / 100
 611 ms 225544 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n;
int fa[maxn][4];
int freq[maxn][3][4];
vector<int> adj[maxn][4];
int rt(int u, int j) {
    if (fa[u][j]==u) return u;
    return fa[u][j] = rt(fa[u][j], j);
}
void merge(int u, int v, int j) {
    int U = rt(u, j), V = rt(v, j);
    if (U!=V) {
        for (int i=0;i<=2;i++) freq[V][i][j] += freq[U][i][j];
        fa[U][j] = V;
    }
    if (adj[u][j].size()<=2) freq[V][adj[u][j].size()][j]--;
    if (adj[v][j].size()<=2) freq[V][adj[v][j].size()][j]--;
    adj[u][j].push_back(v); adj[v][j].push_back(u);
    if (adj[u][j].size()<=2) freq[V][adj[u][j].size()][j]++;
    if (adj[v][j].size()<=2) freq[V][adj[v][j].size()][j]++;
}

void Init(int32_t N) {
    n = N;
    for (int i=0;i<n;i++) for (int j=0;j<=3;j++) fa[i][j] = i, freq[i][0][j] = 1, freq[i][1][j] = freq[i][2][j] = 0;
}

vector<pair<int,int>> track;
bool start = false;
vector<pair<int,bool>> vec = {{-1, 1}};
vector<int> deadgrp = {-1};
bool now = true;
void Link(int32_t u, int32_t v) {
    if (now) track.push_back({u, v});
    int id = -1;
    for (auto &[no, alive]:vec) {
        id++;
        if (u==no || v==no || !alive) continue;
        merge(u, v, id);
        if (!start && (adj[u][id].size()==3 || adj[v][id].size()==3)) {
            start = true;
            if (adj[v][id].size()==3) swap(u, v);
            vec.clear();
            for (int V:adj[u][id]) vec.push_back({V, 1});
            vec.push_back({u, 1});
            for (int i=0;i<n;i++) for (int j=0;j<=3;j++) adj[i][j].clear(), fa[i][j] = i, freq[i][0][j] = 1, freq[i][1][j] = freq[i][2][j] = 0;
            deadgrp = {-1, -1, -1, -1};
            now = false;
            for (auto [x, y]:track) Link(x, y);
            now = true;
            return;
        }
        int U = rt(u, id);
        if (freq[U][1][id]!=2 && freq[U][0][id]!=1) {
            if (start || (deadgrp[id]!=-1 && rt(deadgrp[id], id)!=U)) {
                // cout << u << " " << v << " " << no << endl;
                // cout << freq[U][1][id] << " " << id << endl;
                alive = false;
                continue;
            }
            deadgrp[id] = U;
        }
        if (adj[u][id].size()==4 || adj[v][id].size()==4) {
            if (adj[v][id].size()==4) swap(u, v);
            vec = {{u, 1}};
            for (int i=0;i<n;i++) for (int j=0;j<=3;j++) adj[i][j].clear(), fa[i][j] = i, freq[i][0][j] = 1, freq[i][1][j] = freq[i][2][j] = 0;
            deadgrp = {-1};
            now = false;
            for (auto [x, y]:track) Link(x, y);
            now = true;
        }
    }
}

int32_t CountCritical() {
    if (vec[0].first==-1) {
        if (vec[0].second) return n;
        return 0;
    }
    int ans = 0;
    for (auto [trash, val]:vec) ans += val;
    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96856 KB Output is correct
2 Correct 16 ms 97372 KB Output is correct
3 Correct 15 ms 97376 KB Output is correct
4 Incorrect 13 ms 96856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 150092 KB Output is correct
2 Correct 611 ms 225544 KB Output is correct
3 Correct 137 ms 167044 KB Output is correct
4 Incorrect 490 ms 196016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96856 KB Output is correct
2 Correct 16 ms 97372 KB Output is correct
3 Correct 15 ms 97376 KB Output is correct
4 Incorrect 13 ms 96856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96856 KB Output is correct
2 Correct 16 ms 97372 KB Output is correct
3 Correct 15 ms 97376 KB Output is correct
4 Incorrect 13 ms 96856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 96856 KB Output is correct
2 Correct 16 ms 97372 KB Output is correct
3 Correct 15 ms 97376 KB Output is correct
4 Incorrect 13 ms 96856 KB Output isn't correct
5 Halted 0 ms 0 KB -