Submission #559458

#TimeUsernameProblemLanguageResultExecution timeMemory
559458aryan12Pictionary (COCI18_pictionary)C++17
140 / 140
313 ms32640 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 2e5 + 5; int dp[18][N]; int par[2 * N], values[2 * N]; int Find(int x) { if(par[x] == x) { return x; } return par[x] = Find(par[x]); } void Unite(int a, int b, int pos) { // cout << "Unite(" << a << ", " << b << ", " << pos << ")\n"; values[pos] = a; a = Find(a), b = Find(b); // cout << "rep of a: " << a << ", rep of b: " << b << "\n"; par[a] = par[b] = pos; dp[0][a] = pos; dp[0][b] = pos; } int LCA(int x, int y) { int temp_x = x, temp_y = y; int depth_x = 0, depth_y = 0; for(int i = 17; i >= 0; i--) { if(dp[i][temp_x] != 0) { temp_x = dp[i][temp_x]; depth_x += (1 << i); } if(dp[i][temp_y] != 0) { temp_y = dp[i][temp_y]; depth_y += (1 << i); } } if(depth_y <= depth_x) { swap(depth_x, depth_y); swap(x, y); } int diff = depth_y - depth_x; for(int i = 17; i >= 0; i--) { if((1 << i) & diff) { y = dp[i][y]; } } if(x == y) { return x; } for(int i = 17; i >= 0; i--) { if(dp[i][x] != dp[i][y]) { x = dp[i][x]; y = dp[i][y]; } } return dp[0][x]; } void Solve() { int n, m, q; cin >> n >> m >> q; for(int i = 0; i <= 2 * n; i++) { par[i] = i; } int pos = n + 1; for(int i = m; i > 0; i--) { for(int j = i * 2; j <= n; j += i) { if(Find(i) != Find(j)) { // cout << "uniting: " << i << ", " << j << "\n"; Unite(i, j, pos++); assert(pos <= 2 * n); } } // for(int j = 1; j <= 2 * n; j++) // { // cout << Find(j) << " "; // } // cout << "\n"; } // for(int i = 1; i <= 2 * n; i++) // { // cout << values[i] << " "; // } // cout << "\n"; for(int i = 1; i <= 17; i++) { for(int j = 1; j <= 2 * n; j++) { dp[i][j] = dp[i - 1][dp[i - 1][j]]; } } for(int i = 1; i <= q; i++) { int u, v; cin >> u >> v; // cout << "LCA(u, v) = " << LCA(u, v) << "\n"; cout << m + 1 - values[LCA(u, v)] << "\n"; } } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...