Submission #1046991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046991		onbert	Parachute rings (IOI12_rings)	C++17	0 / 100	659 ms	225392 KiB

rings

#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);
            // if (u==2 && v==3) for (auto [x, y]:vec) cout << x << " " << y << endl;
            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};
            for (auto [x, y]:track) Link(x, y);
        }
    }
}

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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31