Submission #1269157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269157		nerrrmin	Parachute rings (IOI12_rings)	C++20	20 / 100	4096 ms	51324 KiB

rings

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e6 + 10;
int n;
int deg[maxn];
vector < int > g[maxn];
int p[maxn], sz[maxn];
int cnt[maxn][5];
int imp = 0;
int result[maxn], is_problem[maxn], ans;
void Init(int N_)
{

    n = N_;
    imp = 0;
    ans = 0;
    for (int i = 0; i < n; ++ i)
    {
        deg[i] = 0;
        p[i] = i;
        sz[i] = 1;
        result[i] = 1;
        is_problem[i] = 0;
        ans += 1;

    }
}

int find_leader(int i)
{
    if(p[i] == i)return i;
    return (p[i] = find_leader(p[i]));
}
bool connected(int i, int j)
{
    i = find_leader(i);
    j = find_leader(j);
    return (i == j);
}
int problem = 0, recent = -1;
void connect(int i, int j)
{
    int curr_degi = min(4, deg[i]);
    int curr_degj = min(4, deg[j]);
    int new_degi = min(4, deg[i] + 1);
    int new_degj = min(4, deg[j] + 1);
    deg[i] ++;
    deg[j] ++;

    i = find_leader(i);
    j = find_leader(j);
    problem -= is_problem[i];
    problem -= is_problem[j];

    sz[i] += sz[j];
    p[j] = i;
    cnt[i][curr_degi] --;
    cnt[j][curr_degj] --;
    for (int c = 0; c < 5; ++ c)
        cnt[i][c] += cnt[j][c];
    cnt[i][new_degi] ++;
    cnt[i][new_degj] ++;
    if(cnt[i][3] || cnt[i][4] || (cnt[i][2] == sz[i]))
    {
        is_problem[i] ++;
        recent = i;
        problem ++;
    }


}
void Link(int A, int B)
{
    int a = A;
    int b = B;
    g[a].pb(b);
    g[b].pb(a);
    if(!connected(a, b))
    {
        connect(a, b);
    }
    else
    {
        int lead = find_leader(a);
        cnt[lead][min(4, deg[a])] --;
        cnt[lead][min(4, deg[b])] --;
        deg[a] ++;
        deg[b] ++;
        cnt[lead][min(4, deg[a])] ++;
        cnt[lead][min(4, deg[b])] ++;
        ans -= result[lead];
        problem -= is_problem[lead];
        int i = lead;
        if(cnt[i][3] || cnt[i][4] || (cnt[i][2] == sz[i]))
        {
            is_problem[i] ++;
            recent = i;
            problem ++;
        }

    }
}
int block;
int has_cycle = 0;
int used[maxn];
void dfs(int beg, int from)
{
    used[beg] = 1;
    for (auto nb: g[beg])
    {
        if(nb == block || nb == from)continue;
        if(used[nb])has_cycle = 1;
        else dfs(nb, beg);
    }
}
int CountCritical()
{
    int ans = 0;
    for (int i = 0; i <  n; ++ i)
    {
        block = i;
        has_cycle = 0;
        for (auto x: g[i])
            deg[x] --;
        int correct = 1;
        for (int j = 0; j < n; ++ j)
            if(j != block && deg[j] > 2)correct = 0;
        for (int j = 0; j < n; ++ j)
            used[j] = 0;
        for (int j = 0; j < n && correct; ++ j)
        {
            if(used[j])continue;
            if(j == block)continue;
            dfs(j, -1);
            if(has_cycle)correct = 0;
        }
        for (auto x: g[i])
            deg[x] ++;
        ans += correct;
    }
    return ans;

}

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