Submission #543817

#	Time	Username	Problem	Language	Result	Execution time	Memory
543817		Kripton	Split the Attractions (IOI19_split)	C++17	0 / 100	467 ms	1048576 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
vector <int> v[100000];
int rez[100000],mar[100000];
int a,b,c;
void dfscolor(int nod,int papa,int col)
{
    rez[nod]=col;
    for(auto it:v[nod])
        if(it!=papa)
            dfscolor(it,nod,col);
}
void dfs(int nod,int papa)
{
    if(min(a,min(b,c))==0)
        return;
    mar[nod]=1;
    for(auto it:v[nod])
        if(it!=papa)
        {
            dfs(it,nod);
            mar[nod]+=mar[it];
        }
    if(mar[nod]==a)
    {
        a=0;
        mar[nod]=0;
        dfscolor(nod,papa,1);
        return;
    }
    if(mar[nod]==b)
    {
        b=0;
        mar[nod]=0;
        dfscolor(nod,papa,2);
        return;
    }
    if(mar[nod]==c)
    {
        c=0;
        mar[nod]=0;
        dfscolor(nod,papa,3);
        return;
    }
}
void dfsnew(int nod,int papa,int col,int &a)
{
    if(!a)
        return;
    a--;
    rez[nod]=col;
    for(auto it:v[nod])
        if(it!=papa&&!rez[it])
            dfsnew(it,nod,col,a);
}
vector<int> find_split(int n, int A, int B, int C, vector<int> p, vector<int> q)
{
    a=A;
    b=B;
    c=C;
    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);
    vector <int> ans;
    if(min(a,min(b,c))!=0)
    {
        for(i=0; i<n; i++)
            ans.push_back(0);
        return ans;
    }
    for(i=0; i<n; i++)
        if(!rez[i])
        {
            if(a)
                dfsnew(i,-1,1,a);
            else if(b)
                dfsnew(i,-1,2,b);
            else
                dfsnew(i,-1,3,c);
        }
    for(i=0; i<n; i++)
        if(!rez[i])
        {
            if(a)
                rez[i]=1;
            if(b)
                rez[i]=2;
            if(c)
                rez[i]=3;
        }
    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:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     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