Submission #1021289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021289		vjudge1	Split the Attractions (IOI19_split)	C++17	11 / 100	69 ms	13260 KiB

split

#include "split.h"
#include<iostream>
#include<vector>
using namespace std;

int N,rm,v1,v2,c1[4],c2[4],d=-1,e=0,sz[100000],pd[100000];
vector<int>res,ad[100000];

void dfs(int u,int p=-1){
    pd[u]=p;
    sz[u]=1;
    for(auto v:ad[u])if(v!=p&&sz[v]==0){
        dfs(v,u);
        sz[u]+=sz[v];
    }
    if(v2<=sz[u]&&v1<=N-sz[u])d=u,e=2;
    if(v1<=sz[u]&&v2<=N-sz[u])d=u,e=1;
}

void fil(int u,int p,int vl){
    res[u]=vl;
    c2[vl]++;
    for(auto v:ad[u])if(v!=p&&res[v]==0){
        if(c2[vl]==c1[vl])return;
        fil(v,u,vl);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N=n,rm=6;
	c1[1]=a,c1[2]=b,c1[3]=c;
	v1=min(min(a,b),c);
	v2=a+b+c-v1-max(max(a,b),c);
	for(int i=0;i<n;i++)res.push_back(0);
	for(int i=0;i<p.size();i++)
        ad[p[i]].push_back(q[i]),
        ad[q[i]].push_back(p[i]);
	if(a==1){
        fil(0,-1,2);
        for(int i=0;i<n;i++)if(res[i]==0){
            if(c2[1]==0){
                c2[1]=1;
                res[i]=1;
            }else res[i]=3;
        }
	}else{
        dfs(0);
        if(d!=-1){
            if(e==1){
                if(v1==a)fil(d,pd[d],1),rm-=1;
                if(v1==b)fil(d,pd[d],2),rm-=2;
                if(v1==c)fil(d,pd[d],3),rm-=3;
                if(v2==a)fil(pd[d],d,1),rm-=1;
                if(v2==b)fil(pd[d],d,2),rm-=2;
                if(v2==c)fil(pd[d],d,3),rm-=3;
            }else{
                if(v2==a)fil(d,pd[d],1),rm-=1;
                if(v2==b)fil(d,pd[d],2),rm-=2;
                if(v2==c)fil(d,pd[d],3),rm-=3;
                if(v1==a)fil(pd[d],d,1),rm-=1;
                if(v1==b)fil(pd[d],d,2),rm-=2;
                if(v1==c)fil(pd[d],d,3),rm-=3;
            }
            for(int i=0;i<n;i++)if(res[i]==0)res[i]=rm;
        }
	}
	return res;
}

Compilation message (stderr)

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

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