Submission #1047008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047008		onbert	Parachute rings (IOI12_rings)	C++17	0 / 100	663 ms	225452 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};
vector<int> cnt = {0};
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) {
            if (!alive || vec.size()!=4) continue;
            cnt[id]++;
            // cout << vec[id].first << " " << cnt[id] << endl;
            if (cnt[id]==4) {
                vec = {{vec[id].first, 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};
                cnt = {0};
                now = false;
                for (auto [x, y]:track) Link(x, y);
                now = true;
            }
            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();
            cnt.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};
            cnt = {0, 0, 0, 0};
            now = false;
            for (auto [x, y]:track) Link(x, y);
            now = true;
            return;
        }
        int U = rt(u, id);
        if (freq[U][1][id]!=2) {
            if (start || (deadgrp[id]!=-1 && rt(deadgrp[id], id)!=U)) {
                alive = false;
                continue;
            }
            deadgrp[id] = U;
        }
        if (start && adj[u][id].size()>2 || adj[v][id].size()>2) alive = false;
        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};
            cnt = {0};
            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;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int32_t, int32_t)':
rings.cpp:80:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |         if (start && adj[u][id].size()>2 || adj[v][id].size()>2) alive = false;
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31