oj.uz

답안 #557621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557621 2022-05-05T15:48:57 Z Mounir Inside information (BOI21_servers) C++14
2.5 / 100
 491 ms 99288 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 = 19;
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 (b != 0 && ancetres[noeud][b] == -1){
            fill(noeud, b - 1);
            fill(ancetres[noeud][b - 1], b - 1);
            int step = ancetres[noeud][b - 1];
            ancetres[noeud][b] = ancetres[step][b - 1];
            maxArete[noeud][b] = max(maxArete[noeud][b - 1], maxArete[step][b - 1]);
            minArete[noeud][b] = min(minArete[noeud][b - 1], minArete[step][b - 1]);
            lastArete[noeud][b] = lastArete[step][b - 1];
 
            for (int t = 0; t < 2; ++t){
                  if (ok[noeud][b - 1][t] && ok[step][b - 1][t] && bonOrdre(lastArete[noeud][b - 1], maxArete[step][0], t))
                        ok[noeud][b][t] = true;
                  else
                        ok[noeud][b][t] = false;
            }
      }
}
 
vector<int> voisins[N];
vector<int> poids[N];
 
void dfs(int noeud, int pere, int areteAvant, int etage){
      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;
      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 (pow2[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 (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);
      bool OK = true;
      int lastAreteCur = 1e9, maxAreteCur = -1;
      for (int b = B - 1; b >= 0; --b){
            if (lim + pow2[b] <= prof[source] && source != 0){
                  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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 12964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 12964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 12924 KB Output is correct
2 Correct 491 ms 99288 KB Output is correct
3 Correct 483 ms 99188 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 250 ms 12924 KB Output is correct
2 Correct 491 ms 99288 KB Output is correct
3 Correct 483 ms 99188 KB Output is correct
4 Incorrect 183 ms 13004 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 226 ms 12916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 226 ms 12916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 12908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 12908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 224 ms 12924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 224 ms 12924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 12940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 12940 KB Output isn't correct
2 Halted 0 ms 0 KB -