Submission #1190118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190118		alexdd	Split the Attractions (IOI19_split)	C++20	40 / 100	553 ms	1114112 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> con[200005];

int n,a,b,c;
int id[3];
int cntv;
vector<int> visited;
void usor(int nod, int b, int val)
{
    if(cntv==b)
        return;
    visited[nod] = val;
    cntv++;
    for(int adj:con[nod])
        if(!visited[adj])
            usor(adj,b,val);
}
vector<int> solve_toate_mici()
{
    int cntcap=0;
    for(int cap=0;cap<n;cap++)
    {
        if(con[cap].size() == 1)
        {
            cntcap++;
            if(cntcap==1)
            {
                cntv=0;
                usor(cap,a,1);
            }
            else
            {
                cntv=0;
                usor(cap,b,2);
            }
        }
    }
    if(cntcap==0)
    {
        for(int cap=0;cap<n;cap++)
        {
            if(visited[cap]==0 && cntcap<2)
            {
                cntcap++;
                if(cntcap==1)
                {
                    cntv=0;
                    usor(cap,a,1);
                }
                else
                {
                    cntv=0;
                    usor(cap,b,2);
                }
            }
        }
    }
    assert(cntcap==2);
    for(int i=0;i<n;i++)
        if(visited[i]==0)
            visited[i]=3;
    return visited;
}
vector<int> solve_a1()
{
    usor(0,b,2);
    for(int i=0;i<n;i++)
    {
        if(visited[i]==0)
        {
            visited[i]=1;
            break;
        }
    }
    for(int i=0;i<n;i++)
        if(visited[i]==0)
            visited[i]=3;
    return visited;
}

int siz[200005];
void dfs(int nod, int par)
{
    siz[nod]=1;
    for(int adj:con[nod])
    {
        if(adj==par)
            continue;
        dfs(adj,nod);
        siz[nod]+=siz[adj];
    }
}
int root1,root2;
void dfs2(int nod, int par)
{
    if(root1!=-1)
        return;
    if(par!=-1 && siz[nod]>=a && n-siz[nod]>=b)
    {
        root1=nod;
        root2=par;
        return;
    }
    if(par!=-1 && siz[nod]>=b && n-siz[nod]>=a)
    {
        root1=par;
        root2=nod;
        return;
    }
    for(int adj:con[nod])
    {
        if(adj==par)
            continue;
        dfs2(adj,nod);
    }
}
vector<int> solve_arbore()
{
    id[0] = 1;
    id[1] = 2;
    id[2] = 3;
    for(int pas=0;pas<5;pas++)
    {
        if(a > b)
        {
            swap(a,b);
            swap(id[0],id[1]);
        }
        if(b > c)
        {
            swap(b,c);
            swap(id[1],id[2]);
        }
    }

    dfs(0,-1);
    root1=root2=-1;
    dfs2(0,-1);
    if(root1==-1)
        return vector<int>(n,0);
    visited[root1] = id[0];
    visited[root2] = id[1];
    
    cntv=0;usor(root1,a,id[0]);
    cntv=0;usor(root2,b,id[1]);
    for(int i=0;i<n;i++)
        if(visited[i]==0)
            visited[i]=id[2];
    return visited;
}

std::vector<int> find_split(int copn, int copa, int copb, int copc, std::vector<int> p, std::vector<int> q)
{
    a = copa;
    b = copb;
    c = copc;
    n = copn;

    visited.resize(n,0);
    for(int i=0;i<p.size();i++)
    {
        con[p[i]].push_back(q[i]);
        con[q[i]].push_back(p[i]);
    }
    bool all_mici=1;
    for(int i=0;i<n;i++)
        if(con[i].size() > 2)
            all_mici=0;
    if(all_mici)
        return solve_toate_mici();
    else if(a==1)
        return solve_a1();
    return solve_arbore();
}

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