Submission #618019

#	Time	Username	Problem	Language	Result	Execution time	Memory
618019		Richem	Split the Attractions (IOI19_split)	C++14	100 / 100	149 ms	24260 KiB

split

#include "split.h"
#include <iostream>
#include <vector>

using namespace std;

const int MAX_SOMMET = 1e5+42;

vector<int> adj[MAX_SOMMET];

int iEnsemble[3] = {1, 2, 3};
int tEnsemble[3];

int nbSommet, nbArete;

vector<int> arbre[MAX_SOMMET];

bool vu[MAX_SOMMET] = {0};

void calcArbre(int sommet) {
    vu[sommet] = 1;

    for(auto voisin : adj[sommet]) {
        if(!vu[voisin]) {
            arbre[sommet].push_back(voisin);
            arbre[voisin].push_back(sommet);
            calcArbre(voisin);
        }
    }
}

int tailleComp[MAX_SOMMET] = {0};

int calcTaille(int sommet, int pere) {
    tailleComp[sommet] = 1;

    for(auto voisin : arbre[sommet]) {
        if(voisin == pere) continue;

        tailleComp[sommet] += calcTaille(voisin, sommet);
    }

    return tailleComp[sommet];
}

int calcCentroid(int sommet, int pere) {
    for(auto voisin : arbre[sommet]) {
        if(voisin == pere) continue;

        if(tailleComp[voisin] * 2 > nbSommet)
            return calcCentroid(voisin, sommet);
    }

    return sommet;
}

int centroid;

int uf[MAX_SOMMET];
int tailleUf[MAX_SOMMET];

int trouver(int x) {
    if(uf[x] == x)
        return x;
    return uf[x] = trouver(uf[x]);
}

void unir(int a, int b) {
    int pa = trouver(a);
    int pb = trouver(b);

    if(pa != pb) {
        uf[pb] = pa;
        tailleUf[pa] += tailleUf[pb];
    }
}

void initUf(int sommet, int pere) {
    if(pere != centroid && sommet != centroid)
        unir(pere, sommet);

    for(auto voisin : arbre[sommet]) {
        if(voisin == pere) continue;

        initUf(voisin, sommet);
    }
}

int idComp() {
    for(int sommet = 0; sommet < nbSommet; sommet++) {
        if(tailleUf[trouver(sommet)] >= tEnsemble[0] && sommet != centroid)
            return trouver(sommet);
    }
    for(int sommet = 0; sommet < nbSommet; sommet++) {
        for(auto voisin : adj[sommet]) {
            if(sommet == centroid || voisin == centroid) continue;
            unir(sommet, voisin);
            if(tailleUf[trouver(sommet)] >= tEnsemble[0])
                return trouver(sommet);
        }
    }

    return -1;
}

int compA;

vector<int> rep;

bool vuA[MAX_SOMMET] = {0};

int nbRestantA;

void dfsA(int sommet) {
    if(vuA[sommet] || trouver(sommet) != compA || nbRestantA == 0)
        return;
    vuA[sommet] = 1;
    rep[sommet] = iEnsemble[0];
    nbRestantA--;

    for(auto voisin : adj[sommet]) 
        dfsA(voisin);
}

bool vuB[MAX_SOMMET] = {0};
int nbRestantB;

void dfsB(int sommet) {
    if(vuB[sommet] || nbRestantB == 0 || rep[sommet] != 0)
        return;
    vuB[sommet] = 1;
    nbRestantB--;
    rep[sommet] = iEnsemble[1];

    for(auto voisin : adj[sommet])
        dfsB(voisin);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    nbSommet = n, nbArete = p.size();
    tEnsemble[0] = a, tEnsemble[1] = b, tEnsemble[2] = c;

    for(int sommet = 0; sommet < nbSommet; sommet++) {
        tailleUf[sommet] = 1;
        uf[sommet] = sommet;
        rep.push_back(0);
    }

    for(int id : {0, 1, 0}) {
        if(tEnsemble[id] > tEnsemble[id+1]) {
            swap(tEnsemble[id], tEnsemble[id+1]);
            swap(iEnsemble[id], iEnsemble[id+1]);
        }
    }

    for(int id = 0; id < nbArete; id++) {
        adj[p[id]].push_back(q[id]);
        adj[q[id]].push_back(p[id]);
    }


    calcArbre(0);
    calcTaille(0, -1);
    centroid = calcCentroid(0, -1);

    initUf(centroid, -1);

    compA = idComp();

    if(compA == -1) 
        return rep;

    nbRestantA = tEnsemble[0];
    for(auto voisin : adj[centroid]) {
        if(trouver(voisin) == compA) {
            dfsA(voisin);
            break;
        }
    }

    nbRestantB = tEnsemble[1];
    dfsB(centroid);

    for(int sommet = 0; sommet < nbSommet; sommet++) {
        if(rep[sommet] == 0)
            rep[sommet] = iEnsemble[2];
    }

    return rep;
}

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