Submission #1048598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048598		NotLinux	Split the Attractions (IOI19_split)	C++17	100 / 100	143 ms	24444 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
const int inf = 1e9 + 7;
const int LIM1 = 1e5 + 7;
int subt[LIM1] , N , A , B , C , vis[LIM1] , past[LIM1] , depth[LIM1] , high[LIM1];
vector < int > graph[LIM1] , color;
vector < pair < int , int > > wlog(3);
void dfs1(int node , int par){
    subt[node] = 1;
    past[node] = par;
    depth[node] = depth[par] + 1;
    high[node] = depth[node];
    // cout << "dfs1 : " << node << " , " << past[node] << endl;
    for(auto itr : graph[node]){
        if(subt[itr] == -1){
            dfs1(itr , node);
            subt[node] += subt[itr];
        }
        else{
            high[node] = min(high[node] , depth[itr]);
        }
    }
}
vector < set < int > > p(2);
void vectorize(int node , int paint){
    vis[node] = 1;
    p[paint].insert(node);
    for(auto itr : graph[node]){
        if(past[itr] == node and vis[itr] == 0){
            vectorize(itr , paint);
        }
    }
}
int balance = 0 , root = -1;
int sayac0 , sayac1;
void dfs2(int node){
    if((subt[root] - balance - subt[node]) >= wlog[0].first and high[node] < depth[root]){
        balance += subt[node];
        vectorize(node , 1);
    }
    else{
        for(auto itr : graph[node]){
            if(past[itr] == node){
                dfs2(itr);
            }
        }
    }
}
void dfs3(int node){
    // cout << "dfs3 : " << node << endl;
    if(p[0].count(node) and sayac0){
        // cout << "flag0 : " << sayac0 << endl;
        sayac0--;
        color[node] = wlog[0].second;
    }
    if(p[1].count(node) and sayac1){
        // cout << "flag1 : " << sayac1 << endl;
        sayac1--;
        color[node] = wlog[1].second;
    }
    for(auto itr : graph[node]){
        if(past[itr] == node){
            dfs3(itr);
        }
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> ps, vector<int> qs) {
    N = n , A = a , B = b , C = c;
    memset(subt , -1 , sizeof(subt));
    for(int i = 0;i<sz(ps);i++){
        graph[ps[i]].push_back(qs[i]);
        graph[qs[i]].push_back(ps[i]);
        // cout << "edge : " << ps[i] << " " << qs[i] << endl;
    }
    wlog = {{A,0} , {B,1} , {C,2}};
    sort(all(wlog));
    depth[0] = 0;
    dfs1(0 , 0);
    color.assign(N , 0);
    for(int i = 0;i<n;i++){
        if(subt[i] >= wlog[0].first){
            bool bl = 1;
            for(auto itr : graph[i]){
                if(past[itr] == i){
                    bl &= subt[itr] < wlog[0].first;
                }
            }
            if(bl == 0)continue;
            root = i;
            // cerr << "root : " << root << endl;
            dfs2(i);
            vectorize(root , 0);
            vectorize(0 , 1);
            // cout << "p0 : ";for(auto itr : p[0])cout << itr << " ";cout << endl;
            // cout << "p1 : ";for(auto itr : p[1])cout << itr << " ";cout << endl;
            if(p[0].size() > p[1].size())swap(p[0] , p[1]);
            if(p[0].size() < wlog[0].first){// fail
                return color;
            }
            color.assign(N , wlog[2].second);
            sayac0 = wlog[0].first , sayac1 = wlog[1].first;
            dfs3(0);
            for(int i = 0;i<n;i++)color[i]++;
            return color;
        }
    }
    return color;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:100:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |             if(p[0].size() < wlog[0].first){// fail
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~

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