Submission #429166

#	Time	Username	Problem	Language	Result	Execution time	Memory
429166		A_D	Split the Attractions (IOI19_split)	C++14	29 / 100	654 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int N=1e5+100;
vector<int> g[N];
int a[N];
bool vis[N];
vector<int> ret;
ii b[3];
bool ans=0;
vector<ii> vec;
int lim;
void dfs2(int u,int p)
{
    a[u]=1;
    for(auto x:g[u]){
        if(x==p)continue;
        dfs2(x,u);
        a[u]+=a[x];
    }
}
void dfs3(int u,int p,int c)
{
    if(lim==0)return;
    lim--;
    ret[u]=c;
    for(auto x:g[u]){
        if(x==p)continue;
        dfs3(x,u,c);
    }
}
void dfs(int u,int p,int sum)
{
    if(ans)return;
    for(auto x:g[u]){
        if(x==p)continue;
        dfs(x,u,a[0]-a[x]);
    }
    vec.clear();
    if(sum!=0)vec.push_back({sum,p});
    for(auto x:g[u]){
        if(x==p)continue;
        vec.push_back({a[x],x});
    }
    sort(vec.begin(),vec.end());
    if(ans)return;
    if(ans)return;
    for(int i=0;i<vec.size();i++){
        ii x=vec[i];
        if(x.F>=b[0].F&&a[0]-x.F>=b[1].F){
            ans=1;
            lim=b[1].F;
            lim--;
            ret[u]=b[1].S;
            for(auto y:vec){
                if(x==y)continue;
                dfs3(y.S,u,b[1].S);
            }
            lim=b[0].F;
            dfs3(x.S,u,b[0].S);
            break;
        }
    }
}
vector<int> find_split(int n,int A,int B,int C,vector<int> p,vector<int> q){
    ret.resize(n);
    b[0]={A,1};
    b[1]={B,2};
    b[2]={C,3};
    sort(b,b+3);
    for(int i=0;i<n-1;i++){
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    dfs2(0,0);
    dfs(0,0,0);
    if(ans){
        for(int i=0;i<n;i++){
            if(ret[i]==0){
                ret[i]=b[2].S;
            }
        }
    }
    return ret;
}

Compilation message (stderr)

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

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