Submission #1046926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046926		onbert	Parachute rings (IOI12_rings)	C++17	0 / 100	188 ms	89544 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5;
int n;
int fa[maxn];
int freq[maxn][4];
vector<int> adj[maxn];
int rt(int u) {
    if (fa[u]==u) return u;
    return fa[u] = rt(fa[u]);
}
void merge(int u, int v) {
    int U = rt(u), V = rt(v);
    if (U!=V) {
        for (int i=0;i<=3;i++) freq[V][i] += freq[U][i];
        fa[U] = V;
    }
    if (adj[u].size()<=3) freq[V][adj[u].size()]--;
    if (adj[v].size()<=3) freq[V][adj[v].size()]--;
    adj[u].push_back(v); adj[v].push_back(u);
    if (adj[u].size()<=3) freq[V][adj[u].size()]++;
    if (adj[v].size()<=3) freq[V][adj[v].size()]++;
}

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

vector<pair<int,int>> track;
bool die = false;
int one = -1, three = -1, deadgrp = -1;
void Link(int32_t u, int32_t v) {
    if (u==one || v==one || die) return;
    track.push_back({u, v});
    merge(u, v);
    if (three==-1 && adj[u].size()==3) three = u;
    if (three==-1 && adj[v].size()==3) three = v;
    int U = rt(u);
    if (freq[U][1]!=2 || freq[U][3]!=0) {
        if (one!=-1 || (deadgrp!=-1 && rt(deadgrp)!=U)) {die = true; return;}
        deadgrp = U;
    }
    if (one==-1 && adj[u].size()==4 || adj[v].size()==4) {
        if (adj[v].size()==4) swap(u, v);
        one = u;
        for (int i=0;i<n;i++) fa[i] = i, freq[i][0] = 1, freq[i][1] = freq[i][2] = freq[i][3] = 0;
        for (auto [u, v]:track) Link(u, v);
    }
}

int32_t CountCritical() {
    if (die) return 0;
    if (one!=-1) return 1;
    if (three!=-1) {
        // cout << "test " << three << endl;
        vector<int> vec = adj[three];
        vec.push_back(three);
        int ans = 0, U = rt(three);
        // cout << "test3 " << freq[U][0] << " " << freq[U][1] << " " << freq[U][2] << " " << freq[U][3] << endl;
        for (int u:vec) {
            for (int v:adj[u]) {
                int sz = adj[v].size();
                freq[U][sz]--;
                freq[U][sz-1]++;
            }
            freq[U][adj[u].size()]--;
            // cout << "test2 " << u << " " << freq[U][0] << " " << freq[U][1] << " " << freq[U][2] << " " << freq[U][3] << endl;
            if (freq[U][3]==0 && freq[U][1]>=2) {
                ans++;
            }
            for (int v:adj[u]) {
                int sz = adj[v].size();
                freq[U][sz]++;
                freq[U][sz-1]--;
            }
            freq[U][adj[u].size()]++;
        }
        return ans;
    }
    return n;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int32_t, int32_t)':
rings.cpp:45:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |     if (one==-1 && adj[u].size()==4 || adj[v].size()==4) {
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~

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