Submission #490524

#	Time	Username	Problem	Language	Result	Execution time	Memory
490524		Richem	Split the Attractions (IOI19_split)	C++14	0 / 100	6 ms	9676 KiB

split

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_SOMMET = 2e5+42;

int nbSommet, nbArete;

vector<int> adj[MAX_SOMMET];

pair<int, int> taille[3];

bool vu[MAX_SOMMET] = {0};
int centroide = -1;

vector<int> arbre[MAX_SOMMET];

int trouveCentroide(int sommet) {
    vu[sommet] = 1;

    int somme = 0;
    bool bon = 1;

    for(auto fils : adj[sommet]) {
        if(vu[fils])
            continue;

        arbre[sommet].push_back(fils);
        arbre[fils].push_back(sommet);

        int tailleFils = trouveCentroide(fils);
        
        bon = min(bon, tailleFils <= nbSommet/2);
        somme += tailleFils;
    }

    if(nbSommet - somme+1 <= nbSommet/2 && bon) 
        centroide = sommet;

    return somme+1;
}

int uf[MAX_SOMMET] = {0};
int tailleComp[MAX_SOMMET] = {0};

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), pb = trouver(b);

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

int compMax;
int tailleMax = 0;

void calcEnsemble(int sommet, int pere) {
    uf[sommet] = sommet;
    tailleComp[sommet]++;

    if(pere != centroide)
        unir(pere, sommet);

    if(tailleComp[trouver(sommet)] > tailleMax) {
        tailleMax = tailleComp[trouver(sommet)];
        compMax = trouver(sommet);
    }

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

        calcEnsemble(fils, sommet);
    }
}

bool fusion() {
    if(tailleMax >= taille[0].first)
        return 1;


    for(int sommet = 0; sommet < nbSommet; sommet++) {
        for(auto voisin : adj[sommet]) {
            if(sommet == centroide || voisin == centroide)
                continue;

            unir(sommet, voisin);

            if(tailleComp[trouver(sommet)] > tailleMax) {
                tailleMax = tailleComp[trouver(sommet)];
                compMax = trouver(sommet);
            }

            if(tailleMax >= taille[0].first) {
                return 1;
            }       
        }
    }
    return 0;
}

vector<int> reponse;

int nbA;

void dfsA(int sommet) {
    if(reponse[sommet] != 0 || nbA <= 0)
        return;
    reponse[sommet] = taille[0].second;
    nbA--;

    for(auto voisin : adj[sommet]) {
        if(trouver(voisin) == compMax)
            dfsA(voisin);
    }
}

int nbB;

bool vuB[MAX_SOMMET] = {0};

void dfsB(int sommet) {
    if(!vuB[sommet]|| nbB <= 0)
        return;
    reponse[sommet] = taille[1].second;
    vuB[sommet] = 1;

    nbB--;

    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();

    for(int i = 0; i < nbSommet; i++) 
        reponse.push_back(0);

    taille[0] = {a, 1};
    taille[1] = {b, 2};
    taille[2] = {c, 3};

    sort(taille, taille + 3);

    nbA = taille[0].first;
    nbB = taille[1].first;

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

    trouveCentroide(0);
    calcEnsemble(centroide, -1);


    if(fusion()) {
        for(auto voisin : adj[centroide]) {
            if(trouver(voisin) == compMax) {
                dfsA(voisin);
                break;
            }        
        }

        dfsB(centroide);

        for(int sommet = 0; sommet < nbSommet; sommet++) {
            if(reponse[sommet] == 0)
                reponse[sommet] = taille[2].second;
        }
    }

    return reponse;
}

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