Submission #1063190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063190		Ahmed57	Split the Attractions (IOI19_split)	C++17	40 / 100	221 ms	25884 KiB

split

#include "bits/stdc++.h"
using namespace std;
vector<int> adj[100001];
int sz[100001],dep[100001];
int vis[100001];
vector<int> tree[100001];
void precomp(int i,int pr){
    sz[i] =1;
    vis[i] = 1;
    dep[i] = dep[pr]+1;
    for(auto j:adj[i]){
        if(vis[j])continue;
        tree[i].push_back(j);
        tree[j].push_back(i);
        precomp(j,i);
        sz[i]+=sz[j];
    }
}
vector<pair<int,int>> typ[2];
void lol(int i,int pr,int uni,int passed,int de){
    typ[passed].push_back({de,i});
    for(auto j:tree[i]){
        if(j==pr)continue;
        lol(j,i,uni,passed|(j==uni),de+1);
    }
}
mt19937 rnd;
vector<int> find_split(int n, int a, int b, int c, vector<int> p,vector<int> q){
    for(int i = 0;i<p.size();i++){
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    int inda = 1 , indb = 2 , indc = 3;
    if(a>b){swap(a,b);swap(inda,indb);}
    if(b>c){swap(b,c);swap(indb,indc);}
    if(a>b){swap(a,b);swap(inda,indb);}
    if(b>c){swap(b,c);swap(indb,indc);}
    int iter = 40;
    while(iter--){
        for(int i = 0;i<n;i++){
            vis[i] = 0;
            sz[i] = 0;
            tree[i].clear();
            dep[i] = 0;
        }
        typ[0].clear();typ[1].clear();
        int root = rnd()%n;
    precomp(root,root);
    int nod = -1 , pr = -1;
    int mi = 1e9;
    for(int i = 0;i<n;i++){
        for(auto j:tree[i]){
            if(dep[j]<dep[i]){
                if(sz[i]>=a&&mi>=sz[i]){
                    nod = i;
                    pr = j;
                    mi = sz[i];
                }
            }else{
                if(n-sz[j]>=a&&mi>=n-sz[j]){
                    nod = i;
                    pr = j;
                    mi = n-sz[j];
                }
            }
        }
    }
    if(n-mi>=b){
        vector<int> ans(n,0);
        int A = mi;
        int B = n-mi;
        lol(pr,pr,nod,0,1);
        sort(typ[0].begin(),typ[0].end());
        sort(typ[1].begin(),typ[1].end());
        reverse(typ[0].begin(),typ[0].end());
        reverse(typ[1].begin(),typ[1].end());
        int lol = (n-mi)-b;
        int val = c-lol;
        for(int i = 0;i<typ[1].size();i++){
            if(i<val)ans[typ[1][i].second] = indc;
            else ans[typ[1][i].second] = inda;
        }
        for(int i = 0;i<typ[0].size();i++){
            if(i<lol)ans[typ[0][i].second] = indc;
            else ans[typ[0][i].second] = indb;
        }
        return ans;
    }
    }
    vector<int> ans(n,0);
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0;i<p.size();i++){
      |                   ~^~~~~~~~~
split.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i = 0;i<typ[1].size();i++){
      |                       ~^~~~~~~~~~~~~~
split.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0;i<typ[0].size();i++){
      |                       ~^~~~~~~~~~~~~~
split.cpp:70:13: warning: unused variable 'A' [-Wunused-variable]
   70 |         int A = mi;
      |             ^
split.cpp:71:13: warning: unused variable 'B' [-Wunused-variable]
   71 |         int B = n-mi;
      |             ^

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