Submission #543907

#	Time	Username	Problem	Language	Result	Execution time	Memory
543907		Kripton	Split the Attractions (IOI19_split)	C++14	40 / 100	131 ms	25164 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000],arb[100000],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;
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&&!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)
{
    cat+=vlu[nod].second;
    marc2[nod]=val;
    if(cat>=vec[0].second)
        return;
    for(auto it:much[nod])
        if(!marc2[it])
            dfsnushce(it,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);
    int centr=-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])
        vlu[++cnt]= {it,dfscrip(it,centr)};
    for(i=0; i<n; i++)
        if(i!=centr)
            for(auto it:v[i])
                if(where[i]!=where[it])
                    much[where[i]].push_back(where[it]);
    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)
            {
                ok=1;
                for(j=1; j<=cnt; j++)
                    if(marc2[j]==cnt1)
                        dfscolor(vlu[j].first,centr,0);
                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:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(i=0; i<p.size(); i++)
      |              ~^~~~~~~~~

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