Submission #1079420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079420		TlenekWodoru	Split the Attractions (IOI19_split)	C++17	100 / 100	75 ms	19020 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;
void DFS3(int v)
{
    if(zaj[v]){return;}
    zaj[v]=1;
    B.push_back(v);
    for(int som : D[v])
    {
        if(Deep[som]<=Deep[v]){continue;}
        DFS3(som);
    }
}
void DFS2(int v, bool stan)
{
    zaj[v]=1;
    if(stan==0)
    {
        bool cv=0;
        for(int som : D[v])
        {
            if(Deep[som]<Deep[ziom]){cv=1;break;}
        }
        if(cv&&NadMna[ziom]-NadMna[v]>=aa)
        {
            stan=1;
            NadMna[ziom]-=NadMna[v];
        }
    }
    if(stan==0){A.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);
    memset(zaj,0,sizeof(zaj));
    for(int u : A){zaj[u]=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 if((int)B.size()>=aa&&(int)A.size()>=bb)
    {
        for(int i=0;i<bb;i++){Odp[A[i]]=2;}
        for(int i=0;i<aa;i++){Odp[B[i]]=1;}
    }
    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: 24 / 24
• Subtask 5: 36 / 36