Submission #863647

#TimeUsernameProblemLanguageResultExecution timeMemory
8636473omar_ahmedInside information (BOI21_servers)C++17
0 / 100
46 ms4816 KiB
#include <bits/stdc++.h> using namespace std ; #define int long long #define endl '\n' #define all(a) a.begin() , a.end() #define alr(a) a.rbegin() , a.rend() const int N = 2e5 + 10; int n, m, id = 0; vector < int > flatten, depth, st; vector < array < int , 3 >> queries; vector < vector < int >> mx_inc, mx_dec, nxt; vector < vector < pair < int , int >>> adj, increase, decrease; void dfs(int node, int par, int last) { increase[0][node] = decrease[0][node] = {par, last}; depth[node] = depth[par] + 1; st[node] = flatten.size(); flatten.push_back(node); for(auto child : adj[node]) { if(child.first == par) continue; dfs(child.first, node, child.second); flatten.push_back(node); } } void build() { nxt[0] = flatten; for(int i = 1 ; (1ll << i) <= flatten.size() ; i++) { for(int j = 0 ; j + (1ll << i) <= flatten.size() ; j++) { int a = nxt[i - 1][j], b = nxt[i - 1][j + (1ll << (i - 1))]; if(depth[a] < depth[b]) { nxt[i][j] = a; } else { nxt[i][j] = b; } } } } int LCA(int l, int r) { l = st[l], r = st[r]; if (l > r) swap(l, r); int pw = __lg(r - l + 1); int a = nxt[pw][l], b = nxt[pw][r - (1 << pw) + 1]; if(depth[a] < depth[b]) { return a; } else { return b; } } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[LCA(u, v)]; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n >> m; depth = st = vector < int > (n + 2); adj = vector < vector < pair < int , int >>> (n + 1); nxt = vector < vector < int >> (22, vector < int > (n * 2 + 5)); mx_dec = vector < vector < int >> (22, vector < int > (n + 2, 1e9)); mx_inc = vector < vector < int >> (22, vector < int > (n + 2, -1e9)); increase = decrease = vector < vector < pair < int , int >>> (22, vector < pair < int , int >> (n + 1)); for(int i = 0 ; i < m + n - 1 ; i++) { int a, b; string ty; cin >> ty >> a >> b; if(ty == "S") { adj[a].push_back({b, i + 1}); adj[b].push_back({a, i + 1}); } else if(ty == "Q") { queries.push_back({a, b, i + 1}); } } dfs(1, 0, 0), build(); for(int i = 1 ; i <= n ; i++) { mx_dec[0][i] = decrease[0][i].second; // cout << "(" << increase[0][i].first << ", " << increase[0][i].second << "), (" << decrease[0][i].first << ", " << decrease[0][i].second << ")" << endl; } // cout << endl; for(int i = 1 ; i <= 20 ; i++) { for(int j = 1 ; j <= n ; j++) { auto a = increase[i - 1][j]; if(a.first != -1) { auto b = increase[i - 1][a.first]; if(a.second <= b.second) { increase[i][j] = b; } else { increase[i][j] = {-1, -1}; } } a = decrease[i - 1][j]; if(a.first != -1) { auto b = decrease[i - 1][a.first]; if(a.second >= b.second) { decrease[i][j] = b; mx_dec[i][j] = a.second; } else { decrease[i][j] = {-1, -1}; } } // cerr << "(" << increase[i][j].first << ", " << increase[i][j].second << "), (" << decrease[i][j].first << ", " << decrease[i][j].second << ")" << endl; } } for(auto i : queries) { int l = i[0], r = i[1], t = i[2]; int lc = LCA(l, r); int d1 = dist(l, LCA(l, r)); int d2 = dist(r, LCA(l, r)); int val1 = 0; bool check1 = 1; for(int i = 20 ; i >= 0 ; i--) { if(d1 & (1ll << i)) { if(decrease[i][l].first < 0) { check1 = 0; break; } else if(mx_dec[i][l] > t) { check1 = 0; break; } else { val1 = decrease[i][l].second; l = decrease[i][l].first; } } } int val2 = 0; bool check2 = 1; for(int i = 20 ; i >= 0 ; i--) { if(d2 & (1ll << i)) { if(increase[i][r].first < 0) { check2 = 0; break; } else if(increase[i][r].second > t) { check1 = 0; break; } else { val2 = increase[i][r].second; r = increase[i][r].first; } } } cout << (check1 && check2 && val1 >= val2? "yes" : "no") << endl; } return 0 ; }

Compilation message (stderr)

servers.cpp: In function 'void build()':
servers.cpp:30:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 1 ; (1ll << i) <= flatten.size() ; i++) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:31:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int j = 0 ; j + (1ll << i) <= flatten.size() ; j++) {
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:118:13: warning: unused variable 'lc' [-Wunused-variable]
  118 |         int lc = LCA(l, r);
      |             ^~
#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...