Submission #1264899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264899		Noname_1900	Valley (BOI19_valley)	C++20	0 / 100	56 ms	26436 KiB

valley

#include<bits/stdc++.h>
using namespace std;
const int NMAX = 100000;
#define int long long
int nbVilles, nbMagazins, nbRequetes, destination;
struct T {
    int dest, temps, iArete, premDist;
};
vector<T> chemins[NMAX];
bool magazin[NMAX];
//int trouverPlusProche()
vector<int> traceLca;
pair<int, int> posTrace[NMAX];
int iValNoeud;
int noeudVersLca[NMAX];
int lcaVersNoeud[NMAX];
int profondeur[NMAX];
void parcours(int noeud, int anc)
{
    if(anc == -1)
    {
        profondeur[noeud] = 1;
    }
    else
        profondeur[noeud] = profondeur[anc] +1;
    iValNoeud++;
    int valActu = iValNoeud;
    noeudVersLca[noeud] = valActu;
    lcaVersNoeud[valActu] = noeud;
    posTrace[valActu].first = traceLca.size();
    posTrace[valActu].second = traceLca.size();
    traceLca.push_back(valActu);
    for(auto pro : chemins[noeud])
    {
        if(pro.dest == anc) continue;
        parcours(pro.dest, noeud);
        posTrace[valActu].second = traceLca.size();
        traceLca.push_back(valActu);
    }
}
int arbreMin[NMAX*3];
pair<int, int> debFin[NMAX*3];
const int INFINI = 1e15;
int construire(int noeud, int deb, int fin)
{
    debFin[noeud] = {deb, fin};
    if(deb == fin-1)    return arbreMin[noeud] = traceLca[deb];
    int mil = (deb+fin)/2;
    return arbreMin[noeud] = min(construire(noeud*2, deb, mil), construire(noeud*2+1, mil, fin));
}
int trouverMin(int noeud, int deb, int fin)
{
   // cout << "debArbre " << noeud << endl;
    if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))   
    {
       // cout << noeud << " " << arbreMin[noeud] << "\n";;
        return arbreMin[noeud];
    }
    if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))   {
       // cout << noeud << " " << INFINI << "\n";;
        return INFINI;
    }
    int a = min(trouverMin(noeud*2, deb, fin), trouverMin(noeud*2+1, deb, fin));
   // cout << noeud << " " << a << "\n";;
    return a;
}
pair<int, int> arrays[NMAX];
pair<int, int> plusHaut(int iArray)
{
    int a = arrays[iArray].first, b = arrays[iArray].second;
    if(profondeur[a] < profondeur[b])   return {a, b};
    return {b, a};
}
bool liaison(int noeud, int ancetre)
{
    int noeudLca = noeudVersLca[noeud], ancetreLca = noeudVersLca[ancetre];
    int posNoeud = posTrace[noeudLca].first;
    int debA = posTrace[ancetreLca].first, finA = posTrace[ancetreLca].second;
  //  cout << noeud << " a " << ancetre << ' ' << debA << "  " << finA << " : " << posNoeud << endl;
    if((debA <= posNoeud) && (finA >= posNoeud))    return true;
    return false;
}
int lca(int noeud1, int noeud2)
{
  //  cout << noeud1 << " " << noeud2 << endl;
    noeud1 = noeudVersLca[noeud1];
    noeud2 = noeudVersLca[noeud2];
    int pos1 = posTrace[noeud1].first;
    int pos2 = posTrace[noeud2].first;
  //  cout << noeud1 << " : " << pos1 << " " << noeud2 << " : " << pos2 << endl;
    int rep = trouverMin(1, min(pos1, pos2), max(pos1, pos2)+1);
  //  cout << "rep lca : " << rep << endl;
    return lcaVersNoeud[rep];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    iValNoeud = -1;
    cin >> nbVilles >> nbMagazins >> nbRequetes >> destination;
    --destination;
    for(int i = 0; i < nbVilles; i++)   posTrace[i] = {-1, -1};
    for(int i = 0; i < nbVilles-1; i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        --a;
        --b;
        chemins[a].push_back({b, t, i, 0});
        chemins[b].push_back({a, t, i, 0});
        arrays[i] = {a, b};
    }

    for(int i = 0; i < nbMagazins; i++)
    {
        int a;
        cin >> a;
        --a;
        magazin[a] = true;
    }
    parcours(0, -1);
   // for(int i = 0; i < nbVilles; i++)   cout << lcaVersNoeud[i] << " ";
  //  for(int i : traceLca)   cout << lcaVersNoeud[i]+1 << " ";
  //  cout << endl;
    construire(1, 0, traceLca.size());
    
    for(int iRequete = 0; iRequete < nbRequetes; iRequete++)
    {
        //lca dep arrivee + detection si empeche est un ancetre, comparaison des profondeurs
        int routeFerme, depart;
        cin >> routeFerme >> depart;
        --routeFerme;
        --depart;
     //   cout << "deb" << endl;
        int interditDePasse = plusHaut(routeFerme).first, autre = plusHaut(routeFerme).second;
        bool surChemin = ((liaison(depart, interditDePasse) && (liaison(depart, autre)) && (profondeur[depart] > profondeur[interditDePasse]))
         || (liaison(destination, interditDePasse) && (liaison(destination, autre)) && (profondeur[destination] > profondeur[interditDePasse])));//
       // cout << "deb " << depart << " " << destination << " : " << routeFerme << endl;
       // cout << surChemin << " " << lca(depart, destination) << endl;
        if(surChemin && (profondeur[lca(depart, destination)] <= profondeur[interditDePasse]))
        {
            cout << 0 << "\n";
        }
        else
            cout << "escaped" << "\n";
    }
  //  trouverPlusProche(0, -1);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41