Submission #297657

#	Time	Username	Problem	Language	Result	Execution time	Memory
297657		infinite_iq	Split the Attractions (IOI19_split)	C++14	22 / 100	657 ms	1048580 KiB

split

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define C continue 
#define fi first
#define se second 
typedef pair < int , int > pi ;
typedef vector < int > vi ;
#include "split.h"
int n , m ;
pi sz [3] ;
vi v  [100009] ;
int num [100009] , P [100009] ;
void dfs ( int node , int p ) {
        num [node] = 1 ;
        P   [node] = p ;
        for ( auto u : v [node] ) {
                if ( u == p ) C ;
                dfs ( u , node ) ;
                num [node] += num [u] ;
        }
}
int goal = 0 ;
vi ret ;
void who ( int node , int p ) {
        if ( ret .size () == goal ) return ;
        ret .pb ( node ) ;
        for ( auto u : v [node] ) {
                if ( u == p ) C ;
                who ( u , node ) ;
        }
}
vi find_split ( int N , int sz1 , int sz2 , int sz3 , vi p , vi q ) {
        n = N , m = p .size () ;
        sz [0] = { sz1 , 1 } ;
        sz [1] = { sz2 , 2 } ;
        sz [2] = { sz3 , 3 } ;
        sort ( sz , sz + 3 ) ;
        for ( int i = 0 ; i < m ; i ++ ) {
                int a , b ;
                a = p [i] , b = q [i] ;
                v [a] .pb ( b ) ;
                v [b] .pb ( a ) ;
        }
        dfs ( 0 , -1 ) ;
        vi ans ( n , 0 ) ;
        for ( int i = 0 ; i < n ; i ++ ) {
                int dn = num [i] , up = n - num [i] ;
                if ( dn < up ) {
                        if ( dn >= sz [0] .fi && up >= sz [1] .fi ) {
                                ret.clear () ;
                                goal = sz [0] .fi ;
                                who ( i, P [i] ) ;
                                for ( auto u : ret ) ans [u] = sz [0] .se ;
                                ret .clear () ;
                                goal = sz [1] .fi ;
                                who ( P [i] , i ) ;
                                for ( auto u : ret ) ans [u] = sz [1] .se ;
                                for ( auto &u : ans ) {
                                        if ( ! u ) {
                                                u = sz [2] .se ;
                                        }
                                }
                                break ;
                        }
                }
                else {
                        if ( up >= sz [0] .fi && dn >= sz [1] .fi ) {
                                ret .clear () ;
                                goal = sz [0] .fi ;
                                who ( P [i] , i ) ;
                                for ( auto u : ret ) ans [u] = sz [0] .se ;
                                ret .clear () ;
                                goal = sz [1] .fi ;
                                who ( i , P [i] ) ;
                                for ( auto u : ret ) ans [u] = sz [1] .se ;
                                for ( auto &u : ans ) {
                                        if ( ! u ) {
                                                u = sz [2] .se ;
                                        }
                                }
                                break ;
                        }
                }
        }
        return ans ;
}

Compilation message (stderr)

split.cpp: In function 'void who(int, int)':
split.cpp:26:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         if ( ret .size () == goal ) return ;
      |              ~~~~~~~~~~~~~^~~~~~~

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