Submission #1162829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162829		Noname_1900	Mergers (JOI19_mergers)	C++20	10 / 100	102 ms	44928 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int NMAX = 500000+1;
const int INFINI = 1e9;
int boss[NMAX];
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]);
}
int sizeComp[NMAX];
void merge(int a, int b)
{
    a = findBoss(a);
    b = findBoss(b);
    if(a == b)  return;
    if(sizeComp[b]>sizeComp[a])
    {
        swap(a, b);
    }
    sizeComp[a] += sizeComp[b];
    boss[b] = a;
    nbComposantesTotal--;
}
bool vuCompo[NMAX];
vector<int> parcoursVu;
int numero[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];

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];
int dejaVU[NMAX];
bool assure[NMAX];
void parcoursFin(int noeud, int anc)
{
   // cout << noeud << " mkm " << endl;
    for(int pro : chemins[noeud])
    {
       // cout << noeud << " " << pro << endl;
        if(pro == anc)  continue;
       // cout << noeud << " " << pro << endl;
        //*
        if(findBoss(pro) != findBoss(noeud))
        {
            if(!assure[findBoss(noeud)])    nbComposantesTotal --;
            assure[findBoss(noeud)] = true;
        }
            /** */
        parcoursFin(pro, noeud);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    nbComposantesTotal = K;
    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;
        if(prem[famille] == 0)
        {
            prem[famille] = i;
        }
        clubs[famille].push_back(i);
        boss[i] = prem[famille];
        sizeComp[i] = 1;
    }
    parcourir(1, 0);
    base(1, 0, parcoursLCA.size());
   // for(int i : parcoursLCA)    cout << parcoursVersNoeud[i] << " ";
   // cout << endl;
    
    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];
        for(int iElem : clubs[iFamille])
        {
            while(iElem != noeudLCA)
            {
                if(dejaVU[iElem] == iFamille)   break;
                dejaVU[iElem] = iFamille;
                merge(iElem, prem[iFamille]);
                iElem = pere[iElem];
            }
        }
        merge(noeudLCA, prem[iFamille]);
    }
    if(nbComposantesTotal == 1)
    {
        cout << 0;
        return 0;
    }
    /*
    for(int i = 1; i <= N; i++)
    {
        cout << findBoss(i) << " ";
    }
    cout << endl;
    cout << nbComposantesTotal << endl;
    /** */
    int origine = 1;
    while((origine <= N) && (chemins[origine].size() == 1)) origine++;
    parcoursFin(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: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30