Submission #153133

#	Time	Username	Problem	Language	Result	Execution time	Memory
153133		errorgorn	Split the Attractions (IOI19_split)	C++14	40 / 100	122 ms	13928 KiB

split

#include "split.h"
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> ii;
vector<int> al[100005];
int color,num;
vector<int> res;
int subtree[100005];
int parent[100005];
void dfs(int i){
    res[i]=color;
    num--;
    if (!num) return;
    for (vector<int>::iterator it=al[i].begin();it!=al[i].end();it++){
        if (!res[*it]) dfs(*it);
        if (!num) return;
    }
}
void sub(int i,int p){
    parent[i]=p;
    for (vector<int>::iterator it=al[i].begin();it!=al[i].end();it++){
        if (*it==p) continue;
        sub(*it,i);
        subtree[i]+=subtree[*it];
    }
    subtree[i]++;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    res=vector<int> (n,0);
	for (int x=0;x<p.size();x++){
        al[p[x]].push_back(q[x]);
        al[q[x]].push_back(p[x]);
	}
    if (a==1){
        if (b>c) num=c,color=3;
        else num=b,color=2;
        dfs(0);
        color=(color==2)?3:2;
        bool lone=true;
        for (int x=0;x<n;x++){
            if (!res[x]){
                if (lone){
                    lone=false;
                    res[x]=1;
                }
                else{
                    res[x]=color;
                }
            }
        }
    }
    else if (n==p.size()+1){
        vector<ii> col;
        col.push_back(ii(a,1));
        col.push_back(ii(b,2));
        col.push_back(ii(c,3));
        sort(col.begin(),col.end());
        sub(0,-1);
        for (int x=0;x<n;x++){
            if (subtree[x]>=col[0].first && n-subtree[x]>=col[1].first){
                res[x]=col[0].second;
                res[parent[x]]=col[1].second;
                color=col[1].second;
                num=col[1].first;
                dfs(parent[x]);
                color=col[0].second;
                num=col[0].first;
                dfs(x);
                for (int x=0;x<n;x++) if (res[x]==0) res[x]=col[2].second;
                return res;
            }
            else if (subtree[x]>=col[1].first && n-subtree[x]>=col[0].first){
                res[x]=col[1].second;
                res[parent[x]]=col[0].second;
                color=col[1].second;
                num=col[1].first;
                dfs(x);
                color=col[0].second;
                num=col[0].first;
                dfs(parent[x]);
                for (int x=0;x<n;x++) if (res[x]==0) res[x]=col[2].second;
                return res;
            }
        }
        return res;
    }
    else{
        int pos=0;
        for (int x=0;x<n;x++){
            if (al[x].size()==1){
                pos=x;
                break;
            }
        }
        while (a--){
            res[pos]=1;
            if (res[al[pos][0]]==0) pos=al[pos][0];
            else pos=al[pos][1];
        }
        while (b--){
            res[pos]=2;
            if (res[al[pos][0]]==0) pos=al[pos][0];
            else pos=al[pos][1];
        }
        for (int x=0;x<n;x++) if (res[x]==0) res[x]=3;
    }
    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:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<p.size();x++){
               ~^~~~~~~~~
split.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     else if (n==p.size()+1){
              ~^~~~~~~~~~~~

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