Submission #1166847

#TimeUsernameProblemLanguageResultExecution timeMemory
1166847ahmedfouadnewPictionary (COCI18_pictionary)C++20
140 / 140
145 ms17164 KiB
#include "bits/stdc++.h" using namespace std; //#define int long long #define pb push_back #define f first #define s second const int N=3e5+10; int n,m,q; int uu[200005],vv[200005]; int par[200005]; int sz[200005]; int findp(int x) { if(par[x]==x) return x; return par[x]=findp(par[x]); } void join(int u,int v) { u=findp(u); v=findp(v); if(u==v) return; if(sz[u]<sz[v]) swap(u,v); par[v]=u; sz[u]+=sz[v]; sz[v]=0; return; } vector<int>mids[200005]; int x[200005],y[200005]; int bl[200005],br[200005]; signed main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>n>>m>>q; for(int i=1;i<=q;i++) { bl[i]=0; br[i]=m; cin>>x[i]>>y[i]; } bool lesa=1; while(lesa) { lesa=0; for(int i=0;i<=m;i++) mids[i].clear(); for(int i=1;i<=n;i++) sz[i]=1,par[i]=i; for(int i=1;i<=q;i++) { if(bl[i]>=br[i]) continue; lesa=1; int mi=bl[i]+(br[i]-bl[i])/2; mids[mi].pb(i); } for(int i=0;i<=m;i++) { if(i) { int v=m-i+1; for(int j=v;j<=n;j+=v) { /// this totals to nlogn cuz n/1 + n/2 + n/3 + n/4 if(j-v) join(j-v,j); } } for(int jj:mids[i]) { if(findp(x[jj])==findp(y[jj])) { br[jj]=i; } else bl[jj]=i+1; } } } for(int i=1;i<=q;i++) { cout<<bl[i]<<"\n"; } }
#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...