제출 #280457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
280457		CaroLinda	Split the Attractions (IOI19_split)	C++14	22 / 100	615 ms	1048580 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 eb emplace_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 , b , c , n , bestRoot = -1 ;
int sub[MAXN] ;
vector< vector<int> > adj ;
vector<int> vec ;
bool vis[MAXN] ;
multiset<int> s ;

void dfs(int x)
{

    vis[x] = true ;
    auto it = s.lower_bound(b) ;

    if( it != s.end() && *it <= n-a ) bestRoot = x ;

    for(auto e : adj[x] )
    {

        if( vis[e] ) continue ;

        sub[x] = n - sub[e] ;
        s.insert( sub[x] ) ;
        it = s.find( sub[e] ) ;
        s.erase( it ) ;

        dfs(e) ;

        it = s.find(sub[x]) ;
        s.erase( it ) ;
        s.insert( n - sub[x] ) ;

    }

}

void dfsIni(int x, int dad = -1)
{
    sub[x] = 1 ;
    for(auto e : adj[x])
    {
        if(e == dad) continue ;
        dfsIni(e, x) ;
        sub[x] += sub[e] ;
    }

    s.insert(sub[x]) ;

}

void dfsB(int x, int dad = -1 )
{

    if(b > 0) vec[x-1] = 2 , b-- ;
    else vec[x-1] = 3 ;

    for(auto e : adj[x] )
    {
        if(e == dad) continue ;
        dfsB(e, x) ;
    }

}

void dfsFinal(int x, int dad = -1 )
{

    sub[x] = 1 ;

    for(auto e : adj[x])
    {
        if( dad == e ) continue ;
        dfsFinal(e,x) ;
        sub[x] += sub[e] ;
    }

    if( sub[x] >= b && sub[x] <= n-a && b > 0) dfsB(x, dad) ;

}

void dfsAgain(int x, int dad = -1)
{

    if(vec[x-1]  == 0  )
    {
        if(a > 0) vec[x-1] = 1 , a-- ;
        else vec[x-1] = 3 ;
    }

    for(auto e : adj[x])
        if(e != dad) dfsAgain(e,x) ;

}

vector<int> find_split(int N , int A , int B , int C , vector<int> p ,vector<int> q )
{

    n = N ;
    a = A ;
    b = B ;
    c = C ;

    lp(i,0,n) vec.emplace_back(0) ;

    for(int i = 0 ; i <= n ; i++ ) adj.emplace_back( *(new vector<int>) ) ;
    for(int i = 0 ; i < sz(p) ; i++ ) adj[ p[i]+1 ].emplace_back( q[i]+1 ) , adj[ q[i]+1 ].emplace_back(p[i]+1) ;

    dfsIni(1,-1) ;
    dfs(1) ;

    if(bestRoot == -1)
        return vec ;

    dfsFinal(bestRoot, -1) ;
    dfsAgain(bestRoot, -1 ) ;

    return vec ;

}

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