제출 #850735

#제출 시각아이디문제언어결과실행 시간메모리
850735esomerInside information (BOI21_servers)C++17
50 / 100
337 ms68032 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" vector<int> depths; void DFS(int x, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& parent){ for(pair<int, int> p : adj[x]){ int node = p.first; if(node == parent[x].first) continue; parent[node] = {x, p.second}; depths[node] = depths[x] + 1; DFS(node, adj, parent); } } int kth(int a, int dist, vector<vector<int>>& binlift){ for(int k = 0; k < 20; k++){ if((1 << k) & dist){ a = binlift[k][a]; } } return a; } int lca(int a, int b, vector<vector<int>>& binlift){ if(depths[a] < depths[b]){ b = kth(b, depths[b] - depths[a], binlift); }else if(depths[b] < depths[a]){ a = kth(a, depths[a] - depths[b], binlift); } if(a == b) return a; int anc = a; for(int k = 19; k >= 0; k--){ if(binlift[k][a] == binlift[k][b]){ anc = binlift[k][a]; }else{ a = binlift[k][a]; b = binlift[k][b]; } } return anc; } pair<int, int> increasing(int a, int anc, vector<vector<pair<int, int>>>& inc, vector<vector<int>>& binlift, vector<pair<int, int>>& parent){ int dist = depths[a] - depths[anc]; int good = 1; int lst = -1; // cout << "dist "<< dist << endl; for(int k = 0; k < 20; k++){ if((1 << k) & dist){ good = min(good, inc[k][a].first); lst = inc[k][a].second; // cout << "k "<< k << " inc/dec "<< inc[k][a].first << " a "<< a << " good "<< good << endl; // cout << "lst "<< lst << endl; a = binlift[k][a]; if(a != anc && lst > parent[a].second) good = 0; } } return {good, lst}; } pair<int, int> decreasing(int a, int anc, vector<vector<pair<int, int>>>& inc, vector<vector<int>>& binlift, vector<pair<int, int>>& parent){ int dist = depths[a] - depths[anc]; int good = 1; int lst = -1; // cout << "dist "<< dist << endl; for(int k = 0; k < 20; k++){ if((1 << k) & dist){ good = min(good, inc[k][a].first); lst = inc[k][a].second; // cout << "k "<< k << " inc/dec "<< inc[k][a].first << " a "<< a << " good "<< good << endl; // cout << "lst "<< lst << endl; a = binlift[k][a]; if(a != anc && lst < parent[a].second) good = 0; } } return {good, lst}; } void solve(){ int N, K; cin >> N >> K; vector<vector<pair<int, int>>> adj(N); depths.resize(N); vector<tuple<int, int, int>> queries; for(int i = 0; i < N + K - 1; i++){ char c; cin >> c; if(c == 'C'){ cout << "NOT NOW" << endl; return; }else if(c == 'S'){ int a, b; cin >> a >> b; a--; b--; adj[a].push_back({b, i}); adj[b].push_back({a, i}); }else{ int a, d; cin >> a >> d; a--; d--; queries.push_back({a, d, i}); } } vector<pair<int, int>> parent(N, {-1, -1}); depths[0] = 0; DFS(0, adj, parent); vector<vector<int>> binlift(20, vector<int>(N)); for(int k = 0; k < 20; k++){ for(int i = 0; i < N; i++){ if(k == 0) binlift[k][i] = parent[i].first; else{ if(binlift[k-1][i] == -1) binlift[k][i] = -1; else binlift[k][i] = binlift[k-1][binlift[k-1][i]]; } } } vector<vector<pair<int, int>>> inc(20, vector<pair<int, int>>(N)); vector<vector<pair<int, int>>> dec(20, vector<pair<int, int>>(N)); //From node to its ancestors. for(int k = 0; k < 20; k++){ for(int i = 0; i < N; i++){ if(k == 0) inc[k][i] = {1, parent[i].second}; else{ if(binlift[k-1][i] == -1) inc[k][i] = inc[k-1][i]; else{ if(inc[k-1][i].first == 0 || inc[k-1][binlift[k-1][i]].first == 0 || (parent[binlift[k-1][i]].second != -1 && parent[binlift[k-1][i]].second < inc[k-1][i].second)){ inc[k][i].first = 0; }else inc[k][i].first = 1; inc[k][i].second = inc[k-1][binlift[k-1][i]].second; } } } } for(int k = 0; k < 20; k++){ for(int i = 0; i < N; i++){ if(k == 0) dec[k][i] = {1, parent[i].second}; else{ if(binlift[k-1][i] == -1) dec[k][i] = dec[k-1][i]; else{ if(dec[k-1][i].first == 0 || dec[k-1][binlift[k-1][i]].first == 0 || parent[binlift[k-1][i]].second > dec[k-1][i].second){ dec[k][i].first = 0; }else dec[k][i].first = 1; dec[k][i].second = dec[k-1][binlift[k-1][i]].second; } } } } // for(int k = 0; k < 3; k++){ // cout << "k "<< k << endl; // for(int i = 0; i < N; i++){ // cout << "i "<< i << " dec "<< dec[k][i].first << " "<< dec[k][i].second << endl; // cout << "i "<< i << " binlift "<< binlift[k][i] << endl; // } // } // cout << "dec 3 2^1 "<< dec[1][3].first << endl; // cout << "PARENTS"<< endl; // for(int i = 0; i < N; i++){ // cout << "i "<< i << endl; // cout << "parent "<< parent[i].first << " "<< parent[i].second << endl; // } vector<int> ans; for(tuple<int, int, int> t : queries){ int a = get<0>(t); int d = get<1>(t); if(a == d){ ans.push_back(1); continue; } // cout << "a "<< a << " d "<< d << " time "<< get<2>(t) << endl; int anc = lca(a, d, binlift); // cout << "anc "<< anc << endl; int mx = -1; if(anc != a) mx = parent[a].second; pair<int, int> firs = increasing(d, anc, inc, binlift, parent); pair<int, int> sec = decreasing(a, anc, dec, binlift, parent); mx = max(mx, max(firs.second, sec.second)); // cout << "firs "<< firs.first << " "<< firs.second << " sec "<< sec.first << " " << sec.second << " mx "<< mx << endl; if(mx > get<2>(t) || firs.first == 0 || sec.first == 0 || (anc != a && anc != d && sec.second != -1 && firs.second > sec.second)){ ans.push_back(0); }else ans.push_back(1); } for(int x : ans) cout << (x == 1 ? "yes" : "no") << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); solve(); }
#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...