Submission #445396

#TimeUsernameProblemLanguageResultExecution timeMemory
445396OzyInside information (BOI21_servers)C++17
100 / 100
732 ms41764 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i = (a); i <= (b); i++) #define repa(i,a,b) for (int i = (a); i >= (b); i--) #define lli long long #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define MAX 240000 #define costo first #define des second struct x { lli tipo; lli des; lli tiempo; lli id; }; lli n,qq,a,b,cent,cont,t; lli visitados[MAX+2],tam[MAX+2],llego[MAX+2],bit[MAX+2]; char c; queue<lli> cola; vector<pair<lli,lli> > hijos[MAX+2]; vector<x> querys[MAX+2]; pair<lli,lli> res[MAX+2]; void actualiza(lli pos,lli val) { while (pos <= t) { bit[pos] += val; pos += pos&(-pos); } } lli sum(lli pos) { lli r = 0; while (pos > 0) { r += bit[pos]; pos -= pos&(-pos); } return r; } lli buscaCen (lli pos, lli padre, lli mitad) { for (auto h : hijos[pos]){ if (h.des == padre || visitados[h.des] == 1) continue; if (tam[h.des] > mitad) return buscaCen(h.des, pos, mitad); } return pos; } void DFS(lli pos, lli padre) { tam[pos] = 1; for (auto h : hijos[pos]) { if (h.des == padre || visitados[h.des] == 1) continue; DFS(h.des, pos); tam[pos] += tam[h.des]; } } void ami(lli pos, lli padre, lli ant, vector<lli> &nuevos) { nuevos.push_back(pos); for (auto h : hijos[pos]) { if (h.des == padre || visitados[h.des] == 1) continue; if (h.costo > ant) continue; ami(h.des,pos,h.costo,nuevos); } } void aellos(lli pos, lli padre, lli ant, vector<pair<lli,lli> > & acc) { acc.push_back({pos,ant}); for (auto h : hijos[pos]) { if (h.des == padre || visitados[h.des] == 1) continue; if (h.costo < ant) continue; aellos(h.des,pos,h.costo,acc); } } void solve() { lli act; while (!cola.empty()) { act = cola.front(); cola.pop(); DFS(act,0); cent = buscaCen(act,0,tam[act]/2); sort(hijos[cent].begin(), hijos[cent].end()); reverse(hijos[cent].begin(),hijos[cent].end()); vector < pair<lli,lli> > deshacer; for (auto h : hijos[cent]) { if (visitados[h.des] == 1) continue; vector<lli> nuevos; ami(h.des,cent,h.costo,nuevos); for (auto nodo : nuevos) { for (auto q : querys[nodo]) { if (q.tipo == 1) { if (q.des == cent && q.tiempo > h.costo) res[q.id].second = 1; else if (llego[q.des] > 0 && llego[q.des] < q.tiempo) res[q.id].second = 1; } else { res[q.id].second += sum(q.tiempo); if (h.costo < q.tiempo) res[q.id].second++; } } } vector< pair<lli,lli> > accesibles; aellos(h.des,cent,h.costo,accesibles); for ( auto nodo : accesibles) { deshacer.push_back(nodo); llego[nodo.first] = nodo.second; actualiza(nodo.second,1); } } for (auto q : querys[cent]) { if (q.tipo == 1) { if (llego[q.des] > 0 && llego[q.des] < q.tiempo) res[q.id].second = 1; } else { res[q.id].second += sum(q.tiempo); } } for (auto borr : deshacer) { llego[borr.first] = 0; actualiza(borr.second,-1); } visitados[cent] = 1; for (auto h : hijos[cent]) { if (visitados[h.des] == 1) continue; cola.push(h.des); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> qq; t = n+qq-1; cont = 1; rep(i,1,t){ cin >> c; if (c == 'S') { cin >> a >> b; hijos[a].push_back({i,b}); hijos[b].push_back({i,a}); } else if (c == 'Q') { cin >> a >> b; querys[b].push_back({1,a,i,cont}); res[cont].first = 1; if (a == b) res[cont].second = 1; cont++; } else { cin >> a; querys[a].push_back({2,0,i,cont}); res[cont].first = 2; cont++; } } cola.push(1); solve(); cont--; rep(i,1,cont) { if (res[i].first == 2) cout << res[i].second+1 << "\n"; else { if (res[i].second == 1) cout << "yes\n"; else cout << "no\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...