Submission #299461

#	Time	Username	Problem	Language	Result	Execution time	Memory
299461		daniel920712	Split the Attractions (IOI19_split)	C++14	18 / 100	126 ms	13168 KiB

split

#include "split.h"
#include <vector>

using namespace std;
vector < int > Next[100005];
bool have[100005]={0};
int con[100005]={0};
int a,b,c;
vector<int> res;
int now=-1;
void F(int here)
{
    now++;
    if(now<a) res[here]=1;
    else if(now<a+b) res[here]=2;
    else res[here]=3;
    have[here]=1;
    for(auto i:Next[here]) if(!have[i]) F(i);
}
void F2(int here)
{
    now++;
    if(now<b) res[here]=2;
    else return ;
    have[here]=1;
    for(auto i:Next[here]) if(!have[i]) F2(i);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
    int M=p.size(),i,big=0;
    ::a=a;
    ::b=b;
    ::c=c;
	for(i=0;i<N;i++) res.push_back(0);
	for(i=0;i<M;i++)
    {
        Next[p[i]].push_back(q[i]);
        Next[q[i]].push_back(p[i]);
        con[p[i]]++;
        con[q[i]]++;
        big=max(big,con[p[i]]);
        big=max(big,con[q[i]]);
    }

    if(big==2)
    {
        for(i=0;i<N;i++)
        {
            if(con[i]==1)
            {
                F(i);
                return res;
            }
        }
        F(1);
        return res;
    }
    else if(a==1)
    {
        for(i=0;i<N;i++) res[i]=3;
        F2(0);
        for(i=0;i<N;i++)
        {
            if(res[i]==3)
            {
                res[i]=1;
                break;
            }
        }
        return res;
    }
    else
    {
        return res;
    }
	return res;
}

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