Submission #294213

#	Time	Username	Problem	Language	Result	Execution time	Memory
294213		humbertoyusta	Split the Attractions (IOI19_split)	C++14	18 / 100	1985 ms	20044 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;
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);
}

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

    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;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0; i<q.size(); i++){
      |                  ~^~~~~~~~~
split.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0; i<pres.size(); i++){
      |                      ~^~~~~~~~~~~~

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