Submission #251499

#TimeUsernameProblemLanguageResultExecution timeMemory
251499apostoldaniel854Pictionary (COCI18_pictionary)C++14
126 / 140
1552 ms10232 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" const int N = 1e5; int c[1 + N], f[1 + N], p[1 + N], h[1 + N]; vector <pair <int, int>> gr[1 + N]; int ft (int x) { return (f[x] == x) ? x : f[x] = ft (f[x]); } void unite (int x, int y, int cost) { x = ft (x); y = ft (y); if (x != y) { if (rand () % 2) swap (x, y); gr[x].pb ({y, cost}); gr[y].pb ({x, cost}); f[y] = x; } } void dfs (int node, int par) { p[node] = par; h[node] = h[par] + 1; for (pair <int, int> edge : gr[node]) if (edge.first != par) { dfs (edge.first, node); c[edge.first] = edge.second; } } int main () { ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) f[i] = i; for (int i = m; i > 0; i--) for (int j = i; j <= n; j += i) unite (j, i, m -i + 1); dfs (1, 0); while (q--) { int x, y; cin >> x >> y; int ans = 0; while (x != y) { if (h[x] > h[y]) { ans = max (ans, c[x]); x = p[x]; } else { ans = max (ans, c[y]); y = p[y]; } } cout << ans << "\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...