Submission #557596

#	Time	Username	Problem	Language	Result	Execution time	Memory
557596		Mounir	Inside information (BOI21_servers)	C++14	2.50 / 100	587 ms	95960 KiB

servers

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define print(x) cout << #x << " est " << x << endl;
#define x first
#define y second
#define int long long
using namespace std;

const int N = 2e5, B = 18;
int ancetres[N][B], maxArete[N][B], minArete[N][B];
int lastArete[N][B];
bool ok[N][B][2];
int prof[N];

bool bonOrdre(int a, int b, int t){
      return ((a > b)^t);
}

void fill(int noeud, int b){
      if (noeud != - 1 && ancetres[noeud][b] == -1){
            fill(noeud, b - 1);
            fill(ancetres[noeud][b - 1], b - 1);
            ancetres[noeud][b] = ancetres[ancetres[noeud][b - 1]][b - 1];
            maxArete[noeud][b] = max(maxArete[noeud][b - 1], maxArete[ancetres[noeud][b - 1]][b - 1]);
            minArete[noeud][b] = min(minArete[noeud][b - 1], minArete[ancetres[noeud][b - 1]][b - 1]);
            lastArete[noeud][b] = lastArete[ancetres[noeud][b - 1]][b - 1];
            for (int t = 0; t < 2; ++t){
                  if (ok[noeud][b - 1][t] && ok[ancetres[noeud][b - 1]][b - 1][t] && bonOrdre(lastArete[noeud][b - 1], maxArete[ancetres[noeud][b - 1]][0], t))
                        ok[noeud][b][t] = true;
                  else
                        ok[noeud][b][t] = false;
                  if (false)     
                        cout << "LA "<<t<< " " << lastArete[noeud][b - 1] << " " << maxArete[ancetres[noeud][b - 1]][0] << " " << ok[noeud][b][t] << endl;
            }
      }
}

vector<int> voisins[N];
vector<int> poids[N];

void dfs(int noeud, int pere, int areteAvant, int etage){
    //  print(noeud); print(pere);cout << "---"<<endl;
      ancetres[noeud][0] = pere;
      lastArete[noeud][0] = areteAvant;
      maxArete[noeud][0] = minArete[noeud][0] = areteAvant;
      prof[noeud] = etage;
      ok[noeud][0][0] = ok[noeud][0][1] = true;
    //  cout << "la " << endl;
      for (int i = 0; i < sz(voisins[noeud]); ++i){
            int enfant = voisins[noeud][i];
           // print(enfant);
            if (enfant != pere)
                  dfs(enfant, noeud, poids[noeud][i], etage + 1);
      }
}

int getProfLca(int noeud, int voisin){
      if (prof[voisin] < prof[noeud])
            return getProfLca(voisin, noeud);
    //  cout << "req " << noeud << " " << voisin << endl;
      for (int b = B - 1; b >= 0; --b){
            if ((1 << b) <= min(prof[noeud], prof[voisin]) && prof[ancetres[voisin][b]] >= prof[noeud])
                  voisin = ancetres[voisin][b];
      }

  //    cout << "req " << noeud << " " << voisin << endl;

      for (int b = B - 1; b >= 0; --b){
            if ((1 << b) <= prof[noeud] && ancetres[noeud][b] != ancetres[voisin][b]){
                  noeud = ancetres[noeud][b];
                  voisin = ancetres[voisin][b];
            }
      }
      
      if (noeud != voisin)
            noeud = ancetres[noeud][0];
      return prof[noeud];
}

bool getAns(int source, int puis, int borneSup){
      int lim = getProfLca(source, puis);
      //cout << "req " << source << " " << puis << " " << lim << endl;
      bool OK = true;
      int lastAreteCur = 1e9, maxAreteCur = -1;
      for (int b = B - 1; b >= 0; --b){
            if (lim + (1 << b) <= prof[source] && source != 0){
             //     cout << lastAreteCur << " " << maxArete[source][b] << " " << ok[source][b][0] << endl;
                  OK &= (lastAreteCur == 1e9 || lastAreteCur > maxArete[source][b]);
                  OK &= ok[source][b][0];
                  chmax(maxAreteCur, maxArete[source][b]);
                  lastAreteCur = lastArete[source][b];


                  source = ancetres[source][b];
            }
      }

   //   cout << OK << endl;

      int firstArete = -1;
      for (int b = B - 1; b >= 0; --b){
            if (lim + (1 << b) <= prof[puis] && puis != 0){
                  OK &= (firstArete == -1 || firstArete < minArete[puis][b]);
                 // cout << puis << " " << b << " " << ok[puis][b][1] << endl;
                  OK &= ok[puis][b][1];
                  chmax(maxAreteCur, maxArete[puis][b]);
                  firstArete = lastArete[puis][b];


                  puis = ancetres[puis][b];
            } 
      }

    //  print(OK); print(maxAreteCur); print(lastAreteCur); print(firstArete); cout << "-----" << endl;
      return (OK && maxAreteCur <= borneSup && lastAreteCur >= firstArete);
}

int aReq[N], dReq[N], iReqc[N];

signed main(){  
      int nNoeuds, nReqs; cin >> nNoeuds >> nReqs;
      nReqs += nNoeuds - 1;
      int num = 0;
      for (int iReq = 0; iReq < nReqs; ++iReq){
            char t;
            int a, d; cin >> t >> a >> d;
            if (t == 'S'){
                  voisins[a].pb(d);
                  voisins[d].pb(a);
                  poids[a].pb(iReq);
                  poids[d].pb(iReq);
            }
            else {
                  aReq[num] = a;
                  dReq[num] = d;
                  iReqc[num] = iReq;
                  num++;
            }
      }

      dfs(1, 1, 0, 0);
      
      for (int b = 1; b < B; ++b)
            for (int noeud = 1; noeud <= nNoeuds; ++noeud)
                  ancetres[noeud][b] = -1;

      for (int b = 1; b < B; ++b)
            for (int noeud = 1; noeud <= nNoeuds; ++noeud)
                  fill(noeud, b);
      
      for (int i = 0; i < num; ++i){
            if (getAns(aReq[i], dReq[i], iReqc[i]))
                  cout << "yes" << endl;
            else
                  cout << "no" << endl;
      }
      return 0;   
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5