Submission #286670

#	Time	Username	Problem	Language	Result	Execution time	Memory
286670		CaroLinda	Split the Attractions (IOI19_split)	C++14	40 / 100	206 ms	23028 KiB

split

#include <bits/stdc++.h>
#include "split.h"

#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()

const int MAXN = 1e5+10 ;

using namespace std ;

int A[3] , N ;
int sub[MAXN] , cor[MAXN] , pai[MAXN] , tam[MAXN] , idx[3] ;
vector<int> adj[MAXN] , tree[MAXN] ;
bool vis[MAXN] ;
vector<pii> outsideSt ;
bool ok = true ;

void findSt(int x, int d = -1 )
{
    vis[x] = true ;
    sub[x] = 1 ;

    for(auto e : adj[x])
    {
        if(!vis[e])
        {
            tree[x].pb(e) ;
            tree[e].pb(x) ;
            findSt(e,x) ;
            sub[x] += sub[e] ;
        }
        else if( e != d ) outsideSt.pb( mk(x,e) ) ;
    }
}

void colore(int x, int pai, int c )
{
    cor[x] = c ;
    for(auto e : tree[x] )
        if(pai != e) colore(e, x, c ) ;
}

int find(int x)
{
    if(x == pai[x]) return x ;
    return pai[x] = find(pai[x]) ;
}
int join(int x, int y)
{
    x = find(x) ;
    y = find(y) ;

    if(x == y) return x ;

    if(rand() % 2) swap(x,y) ;

    pai[x] = y ;
    tam[y] += tam[x] ;

    return y;

}

void spin(int x)
{

    int mx = -1 ;
    for(auto e : tree[x] )
        if( mx == -1 || sub[mx] < sub[e] ) mx = e ;


    if( sub[mx] >= A[0] && (N-sub[mx]) >= A[0] )
    {
        if( sub[mx] > N-sub[mx] ) colore(mx, x, 1) ;
        else colore(x, mx , 1) ;
    }
    else if( sub[mx] >= A[0] )
    {
        sub[x] = N - sub[mx] ;
        sub[mx] = N ;
        spin(mx) ;
    }
    else
    {
        for(auto e : outsideSt )
        {
            if(e.ff == x || e.ss == x) continue ;

            int newPai = join(e.ff, e.ss );

            if( tam[newPai] < A[0] ) continue ;

            if( tam[newPai] > (N-tam[newPai]) )
            {
                for(int i = 1 ; i <= N ; i++ )
                    if( find(i) == newPai ) cor[i] = 1 ;
            }
            else
            {
                for(int i = 1 ; i <= N ; i++ )
                    if(find(i) != newPai ) cor[i] = 1 ;
            }

            return ;

        }

        ok = false ;

    }

}

void pintando(int x, int y)
{
    vis[x] = true ;

    if( A[ cor[x] ] == 0 ) cor[x] = 2 ;
    else A[ cor[x] ]-- ;

    for(auto e : adj[x] )
        if(!vis[e] && cor[e] == y ) pintando(e,y) ;
}

vector<int> find_split(int n , int a1 , int a2 , int a3 , vector<int> p ,vector<int> q )
{
    A[0] = a1 ;
    A[1] = a2 ;
    A[2] = a3 ;
    idx[0] = 0 ;
    idx[1] = 1 ;
    idx[2] = 2 ;
    N = n ;
    srand(time(0)) ;
    sort(idx, idx+3 , [&](int i, int j) { return A[i] < A[j] ; } ) ;
    sort(A, A+3) ;

    lp(i,1,N+1) pai[i] = i , tam[i] = 1 ;
    for(int i = 0 ; i < sz(p) ; i++ )
    {
        p[i]++ ;
        q[i]++ ;
        adj[ p[i] ].push_back(q[i]) ;
        adj[ q[i] ].pb( p[i] ) ;
    }

    findSt(1) ;
    spin(1) ;

    lp(i,1,N+1) vis[i] = false ;

    lp(i,1,N+1)
        if(cor[i] == 0) { pintando(i,0) ; break ; }

    lp(i,1,N+1)
        if(cor[i] == 1) { pintando(i,1) ; break ; }


    vector<int> vec ;
    if(!ok) idx[0] = idx[1] = idx[2] = -1 ;
    for(int i = 0 ; i < N ; i++ ) vec.pb( idx[cor[i+1]] + 1 ) ;

    return vec ;

}

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