Submission #295424

#	Time	Username	Problem	Language	Result	Execution time	Memory
295424		humbertoyusta	Split the Attractions (IOI19_split)	C++14	40 / 100	1977 ms	20196 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define maxn 100010
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define ll long long
#define ii pair<int,int>
using namespace std;

int maxdegree, mk[maxn], cnt, subt[maxn], staff, N, cy;
vector<int> g[maxn], res, pres;
ii f;

void dfs_1(int u,int p,int d){
    if( mk[u] ) return;
    db(u)
    pres.push_back(u);
    mk[u] = 1;
    f = max( f , { d , u } );
    for( auto v : g[u] )
        if( v != p )
            dfs_1(v,u,d+1);
}

void dfs_2(int u,int limit){
    if( cnt == limit ) return;
    mk[u] = 1;
    cnt ++;
    if( cnt == limit ) return;
    for( auto v : g[u] )
        if( !mk[v] )
            dfs_2(v,limit);
}

void dfs_4(int u,int p,int color,int cx){
    if( cy == cx ) return;
    res[u-1] = color;
    cy++;
    if( cy == cx ) return;
    for( auto v : g[u] )
        if( v != p )
            dfs_4(v,u,color,cx);
}

void dfs_3(int u,int p,int a,int b,int c){
    subt[u] = 1;
    for( auto v : g[u] ){
        if( v == p ) continue;
        dfs_3(v,u,a,b,c);
        subt[u] += subt[v];
    }
    if( subt[u] >= a && N - subt[u] >= b && staff == 0 ){
        cy = 0;
        dfs_4(u,p,1,a);
        cy = 0;
        dfs_4(p,u,2,b);
        staff = 3;
    }
    if( subt[u] >= b && N - subt[u] >= a && staff == 0 ){
        cy = 0;
        dfs_4(u,p,2,b);
        cy = 0;
        dfs_4(p,u,1,a);
        staff = 3;
    }
    if( subt[u] >= a && N - subt[u] >= c && staff == 0 ){
        cy = 0;
        dfs_4(u,p,1,a);
        cy = 0;
        dfs_4(p,u,3,c);
        staff = 2;
    }
    if( subt[u] >= c && N - subt[u] >= a && staff == 0 ){
        cy = 0;
        dfs_4(u,p,3,c);
        cy = 0;
        dfs_4(p,u,1,a);
        staff = 2;
    }
    if( subt[u] >= b && N - subt[u] >= c && staff == 0 ){
        cy = 0;
        dfs_4(u,p,2,b);
        cy = 0;
        dfs_4(p,u,3,c);
        staff = 1;
    }
    if( subt[u] >= c && N - subt[u] >= b && staff == 0 ){
        cy = 0;
        dfs_4(u,p,3,c);
        cy = 0;
        dfs_4(p,u,2,b);
        staff = 1;
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {

    N = n;

    for(int i=0; i<q.size(); i++){
        g[p[i]+1].push_back(q[i]+1);
        g[q[i]+1].push_back(p[i]+1);
    }

    for(int i=1; i<=n; i++){
        maxdegree = max( maxdegree , (int)g[i].size() );
        res.push_back(0);
    }

    if( maxdegree <= 2 ){
        f = { -1 , -1 };
        fill(mk+1,mk+n+1,0);
        dfs_1(1,1,0);
        pres.clear();
        fill(mk+1,mk+n+1,0);
        dfs_1(f.s,f.s,0);
        for(int i=0; i<pres.size(); i++){
            if( i < a ){ res[pres[i]-1] = 1; continue; }
            if( i < a + b ){ res[pres[i]-1] = 2; continue; }
            res[pres[i]-1] = 3;
        }

        return res;
    }

    if( a == 1 ){
        fill(mk+1,mk+n+1,0);
        cnt = 0;
        dfs_2(1,b);
        bool put = 1;
        for(int i=1; i<=n; i++){
            if( mk[i] ){ res[i-1] = 2; continue; }
            if( put ){ res[i-1] = 1; put = 0; continue; }
            res[i-1] = 3;
        }

        return res;
    }

    if( q.size() == n - 1 ){
        dfs_3(1,1,a,b,c);
        if( staff == 1 )
            for(int i=0; i<res.size(); i++)
                if( res[i] == 0 ) res[i] = 1;
        if( staff == 2 )
            for(int i=0; i<res.size(); i++)
                if( res[i] == 0 ) res[i] = 2;
        if( staff == 3 )
            for(int i=0; i<res.size(); i++)
                if( res[i] == 0 ) res[i] = 3;
        return res;
    }

	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0; i<q.size(); i++){
      |                  ~^~~~~~~~~
split.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int i=0; i<pres.size(); i++){
      |                      ~^~~~~~~~~~~~
split.cpp:143:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |     if( q.size() == n - 1 ){
      |         ~~~~~~~~~^~~~~~~~
split.cpp:146:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for(int i=0; i<res.size(); i++)
      |                          ~^~~~~~~~~~~
split.cpp:149:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |             for(int i=0; i<res.size(); i++)
      |                          ~^~~~~~~~~~~
split.cpp:152:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             for(int i=0; i<res.size(); i++)
      |                          ~^~~~~~~~~~~

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