Submission #1164268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164268		Noname_1900	Mergers (JOI19_mergers)	C++20	70 / 100	3100 ms	99000 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int NMAX = 500000+1;
const int INFINI = 1e9;
int boss[NMAX];
int N, K;
vector<int> chemins[NMAX];
int prem[NMAX];
int nbComposantesTotal;
int findBoss(int noeud)
{
    if(boss[noeud] == noeud)    return noeud;
    return boss[noeud] = findBoss(boss[noeud]);
}

bool vuCompo[NMAX];
vector<int> parcoursVu;
int numero[NMAX];
int dansFamille[NMAX];
int nbSuiteMaint;
/*
void parcourir(int noeud, int anc)
{
    nbSuiteMaint++;
    numero[noeud] = nbSuiteMaint;
    int bossNoeud = findBoss(noeud);
    if(vuCompo[bossNoeud])
    {
        while((findBoss(*parcoursVu.rbegin()) != findBoss(bossNoeud))&&(!parcoursVu.empty()))
        {
            merge(bossNoeud, *parcoursVu.rbegin());
            parcoursVu.pop_back();
        }
    }
    else
        vuCompo[bossNoeud] = true;
    parcoursVu.push_back(noeud);

    for(int pro : chemins[noeud])
    {
        if(pro == anc)  continue;
        int res = 0;
        parcourir(pro, noeud);       //Avoir
        parcoursVu.push_back(noeud);
    }
    //AAdapter
}
    /** */
vector<int> parcoursLCA;
int placeDansParc[NMAX];
int parcoursVersNoeud[NMAX];
int pere[NMAX];
void parcourir(int noeud, int anc)
{
    
    pere[noeud] = anc;
    nbSuiteMaint++;
    numero[noeud] = nbSuiteMaint;
    parcoursVersNoeud[nbSuiteMaint] = noeud;
    placeDansParc[noeud] = parcoursLCA.size();
    parcoursLCA.push_back(numero[noeud]);
    for(int pro : chemins[noeud])
    {
        if(pro == anc)  continue;
        parcourir(pro, noeud);
        parcoursLCA.push_back(numero[noeud]);
    }
}
int arbre[NMAX*2+1];
pair<int, int> debFin[NMAX*2+1];
void merge(int a, int b)
{
    a = findBoss(a);
    b = findBoss(b);
    if(a == b)  return;
    if(numero[b] < numero[a])
    {
        swap(a, b);
    }
    boss[b] = a;
    nbComposantesTotal--;
}
int base(int noeud, int deb, int fin)
{
    debFin[noeud] = {deb, fin};
    if(deb == fin-1)    return arbre[noeud] = parcoursLCA[deb];
    int milieu = (deb+fin)/2;
    return arbre[noeud] = min(base(noeud*2, deb, milieu), base(noeud*2+1, milieu, fin));
}
int trouverMin(int noeud, int deb, int fin)
{
    if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))   return INFINI;
    if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))   return arbre[noeud];
    return min(trouverMin(noeud*2, deb, fin), trouverMin(noeud*2+1, deb, fin));
}
vector<int> clubs[NMAX];

bool assure[NMAX];
set<int> cheminsEntreCompo[NMAX];
void faireCompo()
{
    for(int iVal = 1; iVal <= N; iVal++)
    {
        int bossNoeud = findBoss(iVal);
        for(auto pro : chemins[iVal])
        {
            int bossPro = findBoss(pro);
            if(bossPro != bossNoeud)    cheminsEntreCompo[bossNoeud].insert(bossPro);
        }
    }
}

void parcoursFin(int noeud, int anc)
{
   // cout << noeud << " mkm " << endl;
    for(int pro : cheminsEntreCompo[noeud])
    {
       // cout << noeud << " " << pro << endl;
        if(pro == anc)  continue;
       // cout << noeud << " " << pro << endl;
        //*
        if(!assure[noeud])    nbComposantesTotal --;
        assure[noeud] = true;
        
            /** */
        parcoursFin(pro, noeud);
    }
}
//faire un graphique parrapport à composantes
//bool vuCompoNouv[NMAX];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> K;
    nbComposantesTotal = N;
    nbSuiteMaint = 0;
    for(int i = 1; i <= N-1; i++)
    {
        int a, b;
        cin >> a>>b;
        chemins[a].push_back(b);
        chemins[b].push_back(a);
    }
    
    for(int i = 1; i <= N; i++)
    {
        int famille;
        cin >> famille;
        boss[i] = i;
        clubs[famille].push_back(i);
        dansFamille[i] = famille;

    }
    parcourir(1, 0);
    base(1, 0, parcoursLCA.size());
   // for(int i : parcoursLCA)    cout << parcoursVersNoeud[i] << " ";

    for(int iFamille = 1; iFamille <= K; iFamille++)
    {
      //  cout << "deb " << iFamille << endl;
        int minElem = INFINI, maxElem = 0;
        for(int iElem : clubs[iFamille])
        {
            int posElem = placeDansParc[iElem];
            minElem = min(minElem, posElem);
            maxElem = max(maxElem, posElem);
        }
        int lca = trouverMin(1, minElem, maxElem+1);
        int noeudLCA = parcoursVersNoeud[lca];
      //  cout << noeudLCA << endl;
        for(int iElem : clubs[iFamille])
        {
            int deb = iElem;
            while(numero[iElem] > numero[noeudLCA])
            {
                merge(iElem, deb);
                if((findBoss(iElem) != 0) && ((numero[pere[iElem]] > numero[findBoss(iElem)])))
                {
                    iElem = findBoss(iElem);
                }
                else
                {
                    iElem = pere[iElem];
                }
                
            }
        }
        for(int iElem : clubs[iFamille])
        {
            merge(iElem, noeudLCA);
        }
        /*
        for(int i = 1; i <= N; i++)
        {
            cout << findBoss(i) << " ";
        }
        cout << endl;/** */
    }
 //   cout << nbComposantesTotal << endl;
    /*
    for(int i = 1; i <= N; i++)
    {
        cout << findBoss(i) << " ";
    }
    cout << endl;
    /** */
    if(nbComposantesTotal == 1)
    {
        cout << 0;
        return 0;
    }
    /*
    for(int i = 1; i <= N; i++)
    {
        cout << findBoss(i) << " ";
    }
    cout << endl;
    cout << nbComposantesTotal << endl;
    /** */
    faireCompo();
    int origine = 1;
    while((origine <= N) && (cheminsEntreCompo[findBoss(origine)].size() == 1)) origine++;
    parcoursFin(findBoss(origine), 0);
   // cout << nbComposantesTotal<< "\n";
    double rep = nbComposantesTotal;
    double autre = 2;
   // for(int i = 1; i <= N; i++) cout << assure[i] << " ";
    //cout << endl;
    cout << ceil(rep/autre);
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 0 / 30