Submission #256976

#TimeUsernameProblemLanguageResultExecution timeMemory
256976PankinPictionary (COCI18_pictionary)C++14
140 / 140
196 ms25616 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("-O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") */ #define mp make_pair #define ll long long #define ld long double #define pb push_back #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fs first #define sc second #define getfiles ifstream cin("input.txt"); ofstream cout("output.txt"); #define endl '\n' #define pii pair<int, int> const int INF = 2000000005; const ll BIG_INF = 2000000000000000005; const int mod = 1000000007; const int P = 31; const ld PI = 3.141592653589793238462643; const double eps = 1e-9; using namespace std; using namespace __gnu_pbds; bool valid(int x, int y, int n, int m) { return x >= 0 && y >= 0 && x < n && y < m; } mt19937 rng(1999999973); typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int N = 100000 + 50; int n, m, q, ans[N], p[N], x[N], y[N], h[N], dp[N][20], mn[N][20]; vector<pii> g[N]; int find_set(int v) { if (p[v] == v) return v; p[v] = find_set(p[v]); return p[v]; } inline void add_edge(int u, int v, int day) { if (find_set(u) == find_set(v)) return; p[find_set(u)] = find_set(v); g[u].pb(mp(v, day)); g[v].pb(mp(u, day)); } void buildTree(int v, int p, int dist) { mn[v][0] = dist; dp[v][0] = p; for (int j = 1; j < 20; j++) { dp[v][j] = dp[dp[v][j - 1]][j - 1]; mn[v][j] = min(mn[v][j - 1], mn[dp[v][j - 1]][j - 1]); } for (int i = 0; i < g[v].size(); i++) { int to = g[v][i].fs; if (to == p) continue; h[to] = h[v] + 1; buildTree(to, v, g[v][i].sc); } } inline int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); for (int j = 19; j >= 0; j--) { if (h[dp[u][j]] >= h[v]) u = dp[u][j]; } if (u == v) return u; for (int j = 19; j >= 0; j--) { if (dp[u][j] != dp[v][j]) { u = dp[u][j]; v = dp[v][j]; } } return dp[u][0]; } inline int getMinUpper(int v, int p) { int ans = m; for (int j = 19; j >= 0; j--) { if (h[dp[v][j]] >= h[p]) { ans = min(ans, mn[v][j]); v = dp[v][j]; } } return ans; } inline int getMin(int u, int v) { int lc = lca(u, v); return min(getMinUpper(u, lc), getMinUpper(v, lc)); } signed main() { fast_io; cin >> n >> m >> q; for (int i = 1; i <= n; i++) { p[i] = i; } for (int i = 0; i < q; i++) { cin >> x[i] >> y[i]; } for (int i = m; i >= 1; i--) { for (int j = i + i; j <= n; j += i) { add_edge(i, j, i); } } buildTree(1, 1, m); for (int i = 0; i < q; i++) { cout << m + 1 - getMin(x[i], y[i]) << endl; } return 0; }

Compilation message (stderr)

pictionary.cpp: In function 'void buildTree(int, int, int)':
pictionary.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].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...