Submission #760818

#	Time	Username	Problem	Language	Result	Execution time	Memory
760818		alexander707070	Split the Attractions (IOI19_split)	C++14	33 / 100	378 ms	1048576 KiB

split

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,sz[MAXN],br,a,b,c;
vector<int> v[MAXN],ans;
bool ok;
char comp[MAXN],s;

void mark(int x,int p, char d){
    if(br==0)return;

    comp[x]=d; br--;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        mark(v[x][i],x,d);
    }
}

void dfs(int x,int p){
    sz[x]=1;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x);
        sz[x]+=sz[v[x][i]];
    }
    
    if(sz[x]>=a and n-sz[x]>=min(b,c) and ok){
        br=a; mark(x,p,'a'); ok=false;

        if(n-sz[x]>=b){br=b; mark(p,x,'b'); s='c';}
        else {br=c; mark(p,x,'c'); s='b';}

    }else if(sz[x]>=b and n-sz[x]>=min(a,c) and ok){
        br=b; mark(x,p,'b'); ok=false;

        if(n-sz[x]>=a){br=a; mark(p,x,'a'); s='c';}
        else {br=c; mark(p,x,'c'); s='a';}
    }else if(sz[x]>=c and n-sz[x]>=min(a,b) and ok){
        br=c; mark(x,p,'c'); ok=false;

        if(n-sz[x]>=b){br=b; mark(p,x,'b'); s='a';}
        else {br=a; mark(p,x,'a'); s='b';}
    }
}

bool li[MAXN];

void dfs2(int x){
    if(br==0)return;
    li[x]=true;

    comp[x]='b'; br--;
    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i]])dfs2(v[x][i]);
    }
}

vector<int> find_split(int N, int A, int B, int C,vector<int> p,vector<int> q){
    n=N; a=A; b=B; c=C;
    for(int i=0;i<p.size();i++){
        p[i]++; q[i]++;
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }

    ans.resize(n);

    if(a==1){
        br=b;
        dfs2(1);
        for(int i=1;i<=n;i++){
            if(comp[i]!='b' and a==1){
                comp[i]='a'; a=0;
            }else if(comp[i]!='b'){
                comp[i]='c';
            }
        }   
    }else{
        ok=true;
        dfs(1,0);
        if(ok)return ans;
    }

    for(int i=1;i<=n;i++){
        if(comp[i]<'a' or comp[i]>'c')comp[i]=s;
        ans[i-1]=comp[i]-'a'+1;
    }

    return ans;
}

/*
int main(){
    find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
*/


 

Compilation message (stderr)

split.cpp: In function 'void mark(int, int, char)':
split.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
split.cpp: In function 'void dfs(int, int)':
split.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
split.cpp: In function 'void dfs2(int)':
split.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~

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