제출 #1199115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199115		Hanksburger	낙하산 고리들 (IOI12_rings)	C++20	0 / 100	464 ms	212496 KiB

rings

#include <bits/stdc++.h>
using namespace std;
int removed[4], ok[4], n, cycles, phase, ans;
struct graph
{
    vector<int> adj[1000005];
    int par[1000005];
    graph()
    {
        for (int i=1; i<=n; i++)
            par[i]=i;
    }
} *original, *newgraphs[4];
int findPar(int u, graph *g)
{
    return g->par[u]==u?u:(g->par[u]=findPar(g->par[u], g));
}
void addEdge(int u, int v, graph *g)
{
    g->adj[u].push_back(v);
    g->adj[v].push_back(u);
    g->par[findPar(u, g)]=findPar(v, g);
}
int checkEdge(int u, int v, graph *g)
{
    //cout << "check edge " << u << ' ' << v << '\n';
    //for (int i=1; i<=n; i++)
    //    cout << (g->par[i]) << '\n';
    if (g->adj[u].size()==2 || g->adj[v].size()==2)
    //{
    //    cout << "return 0\n";
        return 0;
    //}
    int pu=findPar(u, g), pv=findPar(v, g);
    if (pu==pv)
    //{
    //    cout << "return 0\n";
        return 0;
    //}
    addEdge(u, v, g);
    //cout << "return 1\n";
    return 1;
}
void startPhase(int u)
{
    phase=1;
    removed[0]=u;
    removed[1]=original->adj[u][0];
    removed[2]=original->adj[u][1];
    removed[3]=original->adj[u][2];
    for (int i=0; i<4; i++)
    {
        newgraphs[i]=new graph;
        ok[i]=1;
        for (int j=1; j<=n; j++)
        {
            if (j==removed[i])
                continue;
            for (int u:original->adj[j])
            {
                if (u!=removed[i] && j<u)
                {
                    if (!checkEdge(j, u, newgraphs[i]))
                    {
                        ok[i]=0;
                        break;
                    }
                }
            }
            if (!ok[i])
                break;
        }
    }
}
void Init(int N)
{
    ans=n=N;
    original=new graph;
}
void Link(int u, int v)
{
    u++, v++;
    if (!ans)
        return;
    if (phase)
    {
        for (int i=0; i<4; i++)
        {
            //cout << "remove " << removed[i] << '\n';
            if (ok[i] && !checkEdge(u, v, newgraphs[i]))
                ok[i]=0;
        }
        return;
    }
    if (original->adj[u].size()==2)
    {
        addEdge(u, v, original);
        startPhase(u);
        return;
    }
    if (original->adj[v].size()==2)
    {
        addEdge(u, v, original);
        startPhase(v);
        return;
    }
    int pu=findPar(u, original), pv=findPar(v, original);
    if (pu==pv)
    {
        if (cycles)
        {
            ans=0;
            return;
        }
        cycles=1;
        int cur=u, pre;
        ans=1;
        while (cur!=v)
        {
            ans++;
            if (original->adj[cur].size()==1)
            {
                pre=cur;
                cur=original->adj[cur][0];
            }
            else
            {
                int node1=original->adj[cur][0];
                int node2=original->adj[cur][1];
                if (node1==pre)
                {
                    pre=cur;
                    cur=node2;
                }
                else
                {
                    pre=cur;
                    cur=node1;
                }
            }
        }
    }
    addEdge(u, v, original);
}
int CountCritical()
{
    if (phase)
        return ok[0]+ok[1]+ok[2]+ok[3];
    return ans;
}

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