#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 || a == b);
}
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)
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);
// 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 maxAreteCur = -1, lastAreteCur = -1;
for (int b = B - 1; b >= 0; --b){
if (lim + (1 << b) <= prof[source] && source != 0){
// cout << source << " " << ancetres[source][b] << endl;
lastAreteCur = lastArete[source][b];
OK &= (maxAreteCur < maxArete[source][b]);
OK &= ok[source][b][0];
maxAreteCur = maxArete[source][b];
source = ancetres[source][b];
}
}
// cout << OK << endl;
int minAreteCur = 1e9, firstArete = 1e9;
for (int b = B - 1; b >= 0; --b){
if (lim + (1 << b) <= prof[puis] && puis != 0){
// cout << puis << " " << ancetres[puis][b] << endl;
// cout << lim << " " << (1 << b) << " " << prof[puis] << endl << endl;
firstArete = lastArete[puis][b];
OK &= (minAreteCur > minArete[puis][b]);
OK &= ok[puis][b][1];
minAreteCur = minArete[puis][b];
chmax(maxAreteCur, maxArete[puis][b]);
puis = ancetres[puis][b];
}
}
// print(OK); print(maxAreteCur); 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(dReq[i], aReq[i], iReqc[i]))
cout << "yes" << endl;
else
cout << "no" << endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
212 ms |
12876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
212 ms |
12876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
216 ms |
12940 KB |
Output is correct |
| 2 |
Correct |
560 ms |
95504 KB |
Output is correct |
| 3 |
Correct |
556 ms |
98184 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
216 ms |
12940 KB |
Output is correct |
| 2 |
Correct |
560 ms |
95504 KB |
Output is correct |
| 3 |
Correct |
556 ms |
98184 KB |
Output is correct |
| 4 |
Incorrect |
170 ms |
13136 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
233 ms |
12860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
233 ms |
12860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
218 ms |
12868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
218 ms |
12868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
234 ms |
12980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
234 ms |
12980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
220 ms |
12980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
220 ms |
12980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
