oj.uz

Submission #557600

# Submission time Handle Problem Language Result Execution time Memory
557600 2022-05-05T15:00:51 Z Mounir Inside information (BOI21_servers) C++14
2.5 / 100
 498 ms 95556 KB 
#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 pow2[B];
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 (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];
            
            if (false){
                  cout << "ICII " << maxArete[noeud][b - 1] << " " << ancetres[noeud][b - 1] << endl;
            }

            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 (pow2[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 (pow2[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 + pow2[b] <= prof[source] && source != 0){
        //          cout << lastAreteCur << " " << maxArete[source][b] << " " << ok[source][b][0] << endl;
          //        cout << pow2[b] << endl;
                  OK &= (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 + pow2[b] <= prof[puis] && puis != 0){
                  OK &= (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(){  
      pow2[0] = 1;
      for (int b = 1; b < B; ++b)
            pow2[b] = 2 * pow2[b - 1];
      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 noeud = 1; noeud <= nNoeuds; ++noeud)
            fill(noeud, B - 1);
      
     // cout << maxArete[5][1] << endl;

      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

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 230 ms 13244 KB Output is correct
2 Correct 498 ms 95556 KB Output is correct
3 Correct 450 ms 95524 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 230 ms 13244 KB Output is correct
2 Correct 498 ms 95556 KB Output is correct
3 Correct 450 ms 95524 KB Output is correct
4 Incorrect 197 ms 13124 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 13228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 13228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 13128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 13128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 13188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 13188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 13188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 13188 KB Output isn't correct
2 Halted 0 ms 0 KB -