Submission #1219241

#TimeUsernameProblemLanguageResultExecution timeMemory
1219241jahongirPictionary (COCI18_pictionary)C++20
140 / 140
78 ms26184 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define vi vector<int> #define pb push_back #define pi pair<int,int> #define all(a) a.begin(),a.end() // #define int ll const int mxn = 2e5+10, lg2 = 18; vector<int> g[mxn]; int suc[mxn][lg2], val[mxn]; int tin[mxn], tout[mxn], tim; struct DSU{ vector<int> par; int cur; void init(int n){ par = vector<int>(2*n+10,-1); cur = n; } int get(int u){ if(par[u]<0) return u; return par[u] = get(par[u]); } bool merge(int u, int v, int i){ u = get(u), v = get(v); if(u==v) return false; val[++cur] = i; par[cur] = par[u] + par[v]; par[u] = par[v] = cur; g[cur].pb(u); g[cur].pb(v); return true; } }; void dfs(int u){ tin[u] = tim++; for(int i = 1; i < lg2; i++) suc[u][i] = suc[suc[u][i-1]][i-1]; for(auto v : g[u]){ suc[v][0] = u; dfs(v); } tout[u] = tim; } bool isanc(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; } int getlca(int u, int v){ if(isanc(u,v)) return u; if(isanc(v,u)) return v; for(int i = lg2-1; i >= 0; i--) if(!isanc(suc[u][i],v)) u = suc[u][i]; return suc[u][0]; } void solve(){ int n,m,q; cin >> n >> m >> q; DSU dsu; dsu.init(n); for(int i = m; i; i--){ for(int j = 2*i; j <= n; j+=i) dsu.merge(i,j,m-i+1); } suc[dsu.cur][0] = dsu.cur; dfs(dsu.cur); while(q--){ int u,v; cin >> u >> v; cout << val[getlca(u,v)] << '\n'; } } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; while(t--) 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...