Submission #403873

#TimeUsernameProblemLanguageResultExecution timeMemory
403873wind_reaperInside information (BOI21_servers)C++17
0 / 100
43 ms836 KiB
#include <bits/stdc++.h> using namespace std; int INF = 1000000000; struct DSU{ vector<int> head, par, sz; vector<map<int, int>> data; DSU(int n){ data.resize(n); head.resize(n); par.resize(n); sz.resize(n); for(int i = 0; i < n; i++){ par[i] = i; sz[i] = 1; data[i][i] = -INF; head[i] = INF; } } int get(int x){ return (par[x] == x ? x : get(par[x])); } void unite(int x, int y, int timer){ if(sz[x] < sz[y]) swap(x, y); par[y] = x; head[y] = timer; sz[x] += sz[y]; for(auto& [chunk, t] : data[y]){ data[x][chunk] = timer; } } bool query(int node, int og, int chunk){ // cout << "query" << " " << node << ' ' << og << ' ' << chunk << endl; if(head[node] > head[og] || par[node] == node){ return (data[node][chunk] == 0 ? 0 : data[node][chunk] <= head[og]); } else return query(par[node], og, chunk); } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N, Q; cin >> N >> Q; DSU D(N); int timer = 1; for(int i = 1; i <= N+Q-1; i++){ char type; cin >> type; if(type == 'S'){ int u, v; cin >> u >> v; --u, --v; D.unite(u, v, timer); timer++; } else if(type == 'Q'){ int u, chunk; cin >> u >> chunk; --u, --chunk; cout << (D.query(u, u, chunk) == 0 ? "no" : "yes") << '\n'; } } return 0; }
#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...