Submission #266949

#	Time	Username	Problem	Language	Result	Execution time	Memory
266949		doowey	Split the Attractions (IOI19_split)	C++14	40 / 100	1366 ms	21488 KiB

split

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
pii T[3];

const int N = (int)1e5 + 10;
vector<int> Z[N];
vector<int> C[N];
int subt[N];
int par[N];

void dfs(int u){
    subt[u] = 1;
    random_shuffle(Z[u].begin(), Z[u].end());
    for(auto x : Z[u]){
        if(subt[x] == 0){
            par[x]=u;
            C[x].push_back(u);
            C[u].push_back(x);
            dfs(x);
            subt[u] += subt[x];
        }
    }
}

vector<int> ret;

void solve(int id, int pp, int ass){
    ret[id] = T[ass].se;
    if(T[ass].fi == 0){
        ret[id] = T[2].se;
    }
    else{
        T[ass].fi -- ;
    }
    for(auto x : C[id]){
        if(x == pp) continue;
        solve(x, id, ass);
    }
}

int curn;



vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    ret.resize(n);
    curn = n;
	for(int i = 0 ; i < n; i ++ )
        ret[i] = 0;
	T[0] = mp(a, 1);
	T[1] = mp(b, 2);
	T[2] = mp(c, 3);
	sort(T, T + 3);
	for(int i = 0 ; i < p.size(); i ++ ){
        Z[p[i]].push_back(q[i]);
        Z[q[i]].push_back(p[i]);
	}
	int root;
	vector<pii> degs;
	for(int i = 0 ; i < n; i ++ ){
        degs.push_back(mp((int)Z[i].size(), i));
	}
	for(int it = 0 ; it < n; it ++ ){
        if(n <= 2500){
            root = it;
        }
        else{
            if(it > 50) break;
            if(it <= 20 || degs.empty())
                root = ((int)rng() % n + n) % n;
            else{
                root = degs.back().se;
                degs.pop_back();
            }
        }
        root = ((int)rng() % n + n) % n;
        for(int i = 0 ; i < n; i ++ ){
            subt[i] = 0;
            C[i].clear();
        }
        dfs(root);
        for(int cut = 0; cut < n; cut ++ ){
            if(subt[cut] >= T[0].fi && n - subt[cut] >= T[1].fi){
                solve(cut, par[cut], 0);
                solve(par[cut], cut, 1);
                return ret;
            }
            else if(subt[cut] >= T[1].fi && n - subt[cut] >= T[0].fi){
                solve(cut, par[cut], 1);
                solve(par[cut], cut, 0);
                return ret;
            }
        }
	}
	return ret;
}

Compilation message (stderr)

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

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