Submission #543931

#	Time	Username	Problem	Language	Result	Execution time	Memory
543931		Kripton	Split the Attractions (IOI19_split)	C++14	100 / 100	173 ms	27832 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000],arb[100000];
vector <pair<int,int>> much[100000];
pair <int,int> vec[3];
pair <int,int> vlu[100001];
int rez[100000],mar[100000],tata[100000],marc2[100000],where[100000],cnt,cat,cnt2,centr;
int coada[100000];
bool marc[100000];
void dfscolor(int nod,int papa,int ind)
{
    if(vec[ind].first==0)
        return;
    rez[nod]=vec[ind].second;
    vec[ind].first--;
    for(auto it:arb[nod])
        if(it!=papa&&it!=centr&&!rez[it])
            dfscolor(it,nod,ind);
}
void dfs(int nod,int papa)
{
    mar[nod]=1;
    tata[nod]=papa;
    for(auto it:v[nod])
        if(it!=papa&&!mar[it])
        {
            arb[nod].push_back(it);
            arb[it].push_back(nod);
            dfs(it,nod);
            mar[nod]+=mar[it];
        }
}
void dfsnew(int nod,int papa)
{
    mar[nod]=1;
    for(auto it:arb[nod])
        if(it!=papa)
        {
            dfsnew(it,nod);
            mar[nod]+=mar[it];
        }
}
int dfscrip(int nod,int papa)
{
    int cnt1=1;
    where[nod]=cnt;
    for(auto it:arb[nod])
        if(it!=papa)
            cnt1+=dfscrip(it,nod);
    return cnt1;
}
void dfsnushce(int nod,int val)
{
    if(cat>=vec[0].first)
        return;
    cat+=vlu[nod].second;
    marc2[nod]=val;
    if(cat>=vec[0].first)
        return;
    for(auto it:much[nod])
        if(cat<vec[0].first&&!marc2[it.first])
        {
            coada[++cnt2]=it.second;
            dfsnushce(it.first,val);
        }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    vec[0]= {a,1};
    vec[1]= {b,2};
    vec[2]= {c,3};
    sort(vec,vec+3);
    int i;
    for(i=0; i<p.size(); i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    dfs(0,-1);
    for(i=0; i<n; i++)
    {
        int max1=0,s=1;
        for(auto it:arb[i])
            if(it!=tata[i])
            {
                max1=max(max1,mar[it]);
                s+=mar[it];
            }
        if(max(max1,n-s)<=n/2)
            centr=i;
    }
    dfsnew(centr,-1);
    for(auto it:arb[centr]){
        cnt++;
        vlu[cnt]= {it,dfscrip(it,centr)};
    }
    for(i=0; i<n; i++)
        if(i!=centr)
            for(auto it:v[i])
                if(where[it]&&where[i]!=where[it])
                    much[where[i]].push_back({where[it],it});
    /*for(i=1;i<=cnt;i++){
        cout<<i<<" ";
        for(auto it:much[i])
            cout<<it.first<<" ";
        cout<<'\n';
    }*/
    int cnt1=0,ok=0,j;
    for(i=1; i<=cnt; i++)
        if(!marc2[i])
        {
            cat=0;
            dfsnushce(i,++cnt1);
            if(cat>=vec[0].first)
            {
                //cout<<i<<" "<<cat<<'\n';
                dfscolor(vlu[i].first,centr,0);
                for(j=1; j<=cnt2; j++)
                    dfscolor(coada[j],-1,0);
                ok=1;
                break;
            }
        }
    vector <int> ans;
    ans.clear();
    if(ok==0)
    {
        for(i=0; i<n; i++)
            ans.push_back(0);
        return ans;
    }
    else
    {
        dfscolor(centr,-1,1);
        for(i=0; i<n; i++)
            if(rez[i]==0)
                rez[i]=vec[2].second;
        for(i=0; i<n; i++)
            ans.push_back(rez[i]);
        return ans;
    }
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(i=0; i<p.size(); i++)
      |              ~^~~~~~~~~

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