제출 #1079329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079329		TlenekWodoru	Split the Attractions (IOI19_split)	C++17	40 / 100	78 ms	18260 KiB

split

#include<bits/stdc++.h>
#include "split.h"
using namespace std;
vector<int>D[100009];
int Deep[100009];
int NadMna[100009];
bool zaj[100009];
int n,m,aa,bb,cc;
vector<int>Odp;
vector<int>A,B;
int ziom=-1,jakis=-1;
void DFS3(int v)
{
    if(zaj[v]){return;}
    zaj[v]=1;
    if((int)B.size()<bb){B.push_back(v);}
    for(int som : D[v])
    {
        if(Deep[som]!=Deep[v]+1){continue;}
        DFS3(som);
    }
}
void DFS2(int v, bool stan)
{
    zaj[v]=1;
    if(stan==0)
    {
        int cv=-1;
        if(ziom!=v)
        for(int som : D[v])
        {
            if(Deep[som]<Deep[ziom]){cv=som;break;}
        }
        if(cv!=-1&&NadMna[ziom]-NadMna[v]>=aa)
        {
            if(jakis==-1)
            {
                jakis=cv;
                DFS3(jakis);
                memset(zaj,0,sizeof(zaj));
                for(int u : B)
                {
                    zaj[u]=1;
                }
            }
            if(zaj[cv])
            {
                stan=1;
                NadMna[ziom]-=NadMna[v];
            }
        }
    }
    if(stan==0){A.push_back(v);}
    else{B.push_back(v);}
    for(int som : D[v])
    {
        if(zaj[som]||Deep[som]!=Deep[v]+1){continue;}
        DFS2(som,stan);
    }
}
void DFS(int v)
{
    NadMna[v]=1;
    for(int som : D[v])
    {
        if(Deep[som]!=0){continue;}
        Deep[som]=Deep[v]+1;
        DFS(som);
        NadMna[v]+=NadMna[som];
    }
    if(ziom==-1&&NadMna[v]>=aa){ziom=v;}
}
vector<int>find_split(int N, int aaa, int bbb, int ccc, vector<int>E1, vector<int>E2)
{
    aa=aaa;
    bb=bbb;
    cc=ccc;
    vector<pair<int,int>>H={{aaa,1},{bbb,2},{ccc,3}};
    sort(H.begin(),H.end());
    aa=H[0].first;
    bb=H[1].first;
    cc=H[2].first;
    n=N;
    m=(int)E1.size();
    Odp.resize(n);
    for(int i=0;i<m;i++)
    {
        int a=E1[i],b=E2[i];
        D[a].push_back(b);
        D[b].push_back(a);
    }
    Deep[0]=1;
    DFS(0);
    DFS2(ziom,0);
    if(jakis==-1){DFS3(0);}
    if((int)B.size()>=bb)
    {
        for(int i=0;i<aa;i++){Odp[A[i]]=1;}
        for(int i=0;i<bb;i++){Odp[B[i]]=2;}
    }
    else
    {
        swap(aa,bb);
        swap(H[0],H[1]);
        A.clear();
        B.clear();
        jakis=-1;
        ziom=-1;
        memset(zaj,0,sizeof(zaj));
        memset(Deep,0,sizeof(Deep));
        memset(NadMna,0,sizeof(NadMna));

        Deep[0]=1;
        DFS(0);
        DFS2(ziom,0);
        if(jakis==-1){DFS3(0);}
        if((int)B.size()>=bb)
        {
            for(int i=0;i<aa;i++){Odp[A[i]]=1;}
            for(int i=0;i<bb;i++){Odp[B[i]]=2;}
        }
        else
        {
            for(int i=0;i<n;i++){Odp[i]=0;}
            return Odp;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(Odp[i]==0){Odp[i]=H[2].second;}
        else{Odp[i]=H[Odp[i]-1].second;}
    }
    return Odp;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36