#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |