제출 #1164332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164332		Noname_1900	Mergers (JOI19_mergers)	C++20	70 / 100	207 ms	98928 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 nbComposantesTotal;
int findBoss(int noeud)
{
    if(boss[noeud] == noeud)    return noeud;
    return boss[noeud] = findBoss(boss[noeud]);
}

int numero[NMAX];
int dansFamille[NMAX];
int nbSuiteMaint;

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] << " ";
//    int nbCompter = 0;
    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;
            iElem = findBoss(iElem);
            while(numero[iElem] > numero[noeudLCA])
            {
                iElem = pere[iElem];
                iElem = findBoss(iElem);
                merge(iElem, deb);
                
               // nbCompter++;
            }
        }

        /*
        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) << "\n";
   // cout << nbCompter;
}

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