Submission #102360

#TimeUsernameProblemLanguageResultExecution timeMemory
102360ubiratan37Pictionary (COCI18_pictionary)C++11
0 / 140
97 ms8208 KiB
#include <bits/stdc++.h> #define int long long #define double long double #define ff first #define ss second #define endl '\n' #define ii pair<int, int> #define mp make_pair #define mt make_tuple #define DESYNC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define pb push_back #define vi vector<int> #define vii vector< ii > #define EPS 1e-9 #define INF 1e18 #define ROOT 1 #define M 1000000007 const double PI = acos(-1); using namespace std; inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; } int gcd(int a, int b){ if(a == 0) return b; else return gcd(b%a, a); } int uf[112345]; int sz[112345]; int mx[112345]; vector<int> g[112345]; int L[112345]; int find(int u){ if(uf[u] == u) return u; else return find(uf[u]); } void init(int n, int m){ for(int i=0; i<=n; i++){ uf[i] = i; sz[i] = 1; mx[i] = 0; } } int maxl = 0; void merge(int x, int y, int t){ int a = find(x); int b = find(y); if(a == b) return; if(sz[a] < sz[b]) swap(a,b); uf[b] = a; sz[a] += sz[b]; mx[a] = t; } void go(int u, int l){ L[u] = l; maxl = max(maxl, l); for(int v : g[u]){ go(v, l+1); } } int32_t main(){ DESYNC; int n,m; cin >> n >> m; init(n,m); for(int i=m; i>=1; i--){ for(int j=i; j<=n; j+=i){ merge(i, j, m - i + 1); } } for(int i=1; i<=n; i++){ //cout << "i + uf[i]" << i << " + " << uf[i] << endl; if(uf[i] != i){ g[uf[i]].pb(i); } } go(find(1), 1); int q; cin >> q; while(q--){ int ans = 0; int u,v; cin >> u >> v; if(u == v){ cout << 0 << endl; } else { while(u != v){ if(L[u] > L[v]){ ans = max(ans, mx[u]); u = uf[u]; } else { ans = max(ans, mx[v]); v = uf[v]; } } ans = max(ans, mx[u]); cout << ans << endl; } } }
#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...