#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 (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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
12876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
13092 KB |
Output is correct |
| 2 |
Correct |
489 ms |
99184 KB |
Output is correct |
| 3 |
Correct |
535 ms |
99096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
207 ms |
13092 KB |
Output is correct |
| 2 |
Correct |
489 ms |
99184 KB |
Output is correct |
| 3 |
Correct |
535 ms |
99096 KB |
Output is correct |
| 4 |
Incorrect |
166 ms |
13144 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
271 ms |
12900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
271 ms |
12900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
13072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
13072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
12876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
12876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
12928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
12928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
