oj.uz

Submission #557575

# Submission time Handle Problem Language Result Execution time Memory
557575 2022-05-05T13:45:19 Z Mounir Inside information (BOI21_servers) C++14
0 / 100
 213 ms 13244 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 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);
            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)
                  ok[noeud][b][t] = ok[noeud][b - 1][t]&ok[ancetres[noeud][b - 1]][b - 1][t]&bonOrdre(lastArete[noeud][b - 1], maxArete[noeud][0], t);
      }
}

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);
      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];
      }

      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);
      bool OK = true;
      int maxAreteCur = 0, lastAreteCur = -1;
      for (int b = B - 1; b >= 0; --b){
            if (lim + (1 << b) <= prof[source]){
                  lastAreteCur = lastArete[source][b];
                  OK &= (maxAreteCur < maxArete[source][b]);
                  OK &= ok[source][b][0];
                  maxAreteCur = maxArete[source][b];
                  source = ancetres[source][b];
            }
      }

      int minAreteCur = 1e9, firstArete = 1e9;
      for (int b = B - 1; b >= 0; --b){
            if (lim + (1 << b) <= prof[puis]){
                  firstArete = lastArete[source][b];
                  OK &= (minAreteCur > minArete[puis][b]);
                  OK &= ok[puis][b][1];
                  minAreteCur = minArete[puis][b];
                  chmax(maxAreteCur, maxArete[puis][b]);
                  puis = ancetres[puis][b];
            } 
      }

      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)
                  fill(noeud, b);
      
      for (int i = 0; i < num; ++i){
            if (getAns(dReq[i], aReq[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 207 ms 13220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

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

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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