Submission #111346

#TimeUsernameProblemLanguageResultExecution timeMemory
111346aleksamiPictionary (COCI18_pictionary)C++14
56 / 140
1569 ms66560 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 typedef pair<int,int> pii; int n,m,q; vector <int> comps[MAXN]; int par[MAXN]; vector <pii> events[MAXN]; void init() { for(int i = 1; i <= n; i++)comps[i].push_back(i),par[i]=i,events[i].push_back({0,i}); } int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> q; init(); for(int i = m; i >= 1; i--) { int mx = par[i]; for(int j = i; j <= n; j+=i) { if(comps[mx].size()>comps[par[j]].size())mx=par[j]; } for(int j = i; j <= n; j+=i) { if(par[j]==mx)continue; int compid = par[j]; for(auto x:comps[compid]) { comps[mx].push_back(x); par[x]=mx; events[x].push_back({m-i+1,mx}); } //comps[compid].clear(); } } while(q--) { int a,b; cin >> a >> b; int ans = m; for(auto x:events[a]) { for(auto y:events[b]) { if(x.second==y.second)ans=min(ans,max(x.first,y.first)); } } cout << ans << " "; } 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...