제출 #50135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50135		top34051	낙하산 고리들 (IOI12_rings)	C++17	52 / 100	4018 ms	117636 KiB

rings

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

int n, m, mx;
vector<int> way[maxn];
pair<int,int> e[maxn];

int cysz, ban[5], bad[5], cyc[5];
int head[5][maxn], sz[5][maxn], deg[5][maxn];

void Init(int _n) {
    n = _n;
    for(int k=0;k<=4;k++) {
        for(int i=1;i<=n;i++) {
            head[k][i] = i;
            sz[k][i] = 1;
        }
    }
}

int CountCritical() {
    if(mx<=2) {
        if(cyc[0]==0) return n;
        if(cyc[0]==1) return cysz;
        return 0;
    }
    else {
        int res = 0;
        for(int i=1;i<=4;i++) res += !bad[i];
        return res;
    }
}

int findhead(int k, int x) {
    if(head[k][x]==x) return x;
    return head[k][x] = findhead(k, head[k][x]);
}

void edge(int k, int u, int v) {
    if(ban[k]==u || ban[k]==v) return ;

    ++deg[k][u]; ++deg[k][v];
    if(deg[k][u]==3) bad[k] = 1;
    if(deg[k][v]==3) bad[k] = 1;

    int x = findhead(k,u), y = findhead(k,v);
    if(x==y) {
        bad[k] = 1;
        cyc[k]++;
        if(k==0) cysz = sz[k][x];
    }
    else {
        sz[k][y] += sz[k][x];
        head[k][x] = y;
    }
}

void build(int x) {
    ban[1] = x;
    for(int i=0;i<3;i++) ban[i+2] = way[x][i];
    for(int i=1;i<=m;i++) {
        for(int k=1;k<=4;k++) edge(k,e[i].first,e[i].second);
    }
}

void Link(int x, int y) {
    x++; y++;
    way[x].push_back(y); way[y].push_back(x);
    e[++m] = {x,y};

    edge(0,x,y);

    if(mx<=2) {
        if(way[x].size()==3) build(x);
        else if(way[y].size()==3) build(y);
    }
    else {
        for(int k=1;k<=4;k++) edge(k,x,y);
    }

    mx = max(mx, (int)way[x].size());
    mx = max(mx, (int)way[y].size());
}

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