Submission #714931

#TimeUsernameProblemLanguageResultExecution timeMemory
714931stevancvInside information (BOI21_servers)C++14
50 / 100
374 ms39040 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 120000 + 2; const int inf = 1e9; vector<array<int, 2>> g[N]; int par[N][17], in[N], out[N], val[N], donji[N], dep[N], tsz; bool inc[N][17], dek[N][17]; void Dfs(int s, int e) { in[s] = ++tsz; par[s][0] = e; inc[s][0] = 1; dek[s][0] = 1; for (int i = 1; i < 17; i++) { int u = par[s][i - 1]; par[s][i] = par[u][i - 1]; inc[s][i] = inc[s][i - 1] & inc[u][i - 1] & (donji[u] < val[u]); dek[s][i] = dek[s][i - 1] & dek[u][i - 1] & (donji[u] > val[u]); } for (auto zz : g[s]) { int u = zz[0]; int i = zz[1]; if (u == e) continue; dep[u] = dep[s] + 1; donji[s] = i; val[u] = i; Dfs(u, s); } out[s] = tsz; } bool Ancestor(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; } int Lca(int u, int v) { if (Ancestor(u, v)) return u; if (Ancestor(v, u)) return v; for (int i = 16; i >= 0; i--) { if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i]; } return par[u][0]; } int Kth(int u, int k) { for (int i = 16; i >= 0; i--) { if ((1 << i) & k) u = par[u][i]; } return u; } bool MozeI(int u, int v) { if (u == v) return 1; int r = dep[u] - dep[v]; bool ans = 1; for (int i = 16; i >= 0 && ans; i--) { if ((1 << i) & r) { ans &= inc[u][i]; r -= (1 << i); if (r != 0) ans &= (val[Kth(u, (1 << i) - 1)] < val[par[u][i]]); u = par[u][i]; } } return ans; } bool MozeD(int u, int v) { if (u == v) return 1; int r = dep[u] - dep[v]; bool ans = 1; for (int i = 16; i >= 0 && ans; i--) { if ((1 << i) & r) { ans &= dek[u][i]; r -= (1 << i); if (r != 0) ans &= (val[Kth(u, (1 << i) - 1)] > val[par[u][i]]); u = par[u][i]; } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; vector<array<int, 3>> all; int cnt = 0; for (int i = 0; i < n + k - 1; i++) { char ch; cin >> ch; int u, v; if (ch == 'C') { cin >> u; continue; } cin >> u >> v; if (ch == 'S') { g[u].push_back({v, cnt}); g[v].push_back({u, cnt}); all.push_back({0, u, v}); cnt += 1; } else all.push_back({1, u, v}); } Dfs(1, 0); cnt = 0; for (int i = 0; i < all.size(); i++) { if (all[i][0] == 0) { cnt += 1; continue; } int u = all[i][1]; int v = all[i][2]; swap(u, v); if (u == v) { cout << "yes" << en; continue; } int lca = Lca(u, v); int uu, vv; uu = vv = -1; if (u != lca) uu = val[Kth(u, dep[u] - dep[lca] - 1)]; if (v != lca) vv = val[Kth(v, dep[v] - dep[lca] - 1)]; bool ans = MozeI(u, lca) & MozeD(v, lca); if (uu != -1 && vv != -1) ans &= uu < vv; int lst = val[v]; if (v == lca) lst = uu; ans &= lst < cnt; if (ans) cout << "yes" << en; else cout << "no" << en; } return 0; }

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#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...