Submission #543878

#	Time	Username	Problem	Language	Result	Execution time	Memory
543878		Kripton	Split the Attractions (IOI19_split)	C++14	0 / 100	7 ms	9940 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000],arb[100000];
pair <int,int> vec[3];
int rez[100000],mar[100000],tata[100000];
bool marc[100000];
int daddy[100000],sz[100000],strt[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 fada(int nod)
{
    if(daddy[nod]==nod)
        return nod;
    return daddy[nod]=fada(daddy[nod]);
}
void join(int a,int b)
{
    int ra=fada(a),rb=fada(b);
    if(sz[ra]>sz[rb])
    {
        sz[ra]+=sz[rb];
        daddy[rb]=ra;
        strt[ra]+=strt[rb];
    }
    else
    {
        sz[rb]+=sz[ra];
        daddy[ra]=rb;
        strt[rb]+=strt[ra];
    }
}
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[it])
        {
            max1=max(max1,mar[it]);
            s+=mar[it];
        }
        if(max(max1,n-s)<=n/2)
            centr=i;
    }
    assert(centr!=-1);
    dfsnew(centr,-1);
    for(auto it:arb[centr])
        marc[it]=1;
    for(i=0; i<n; i++)
    {
        daddy[i]=i;
        sz[i]=1;
        strt[i]=mar[i];
    }
    for(auto it:arb[centr])
        for(auto it2:v[it])
            if(marc[it2]&&fada(it2)!=fada(it))
                join(it,it2);
    int ok=0;
    for(auto it:arb[centr])
        if(strt[fada(it)]>=vec[0].first)
        {
            ok=1;
            for(auto it2:arb[centr])
            {
                if(fada(it2)==fada(it))
                    dfscolor(it2,centr,0);
                if(!vec[0].first)
                    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:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(i=0; i<p.size(); i++)
      |              ~^~~~~~~~~

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