#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<vector<int>> muchii;
int comp[100005],myroot[100005],dp[17][100005],val[100005],par[100005],niv[100005],lg[100005];
vector<int> used;
int n,m;
int what;
int LCA(int a,int b)
{
if(niv[a]<niv[b])
swap(a,b);
int dif=niv[a]-niv[b];
int loga=log2(dif);
for(int i=0;i<=loga;i++)
if((dif>>i)&1)
a=dp[i][a];
if(a==b)
return a;
loga=log2(niv[a]);
for(int i=loga;i>=0;i--)
if(dp[i][a]!=0&&dp[i][b]!=0)
if(dp[i][a]!=dp[i][b])
{
a=dp[i][a];
b=dp[i][b];
}
return par[a];
}
ll baza=100013;
const ll mod=1e9+7;
int gethash(int a,int b)
{
ll x=(1LL*baza*a)%mod;
x+=b;
if(x>=mod)
x-=mod;
return x;
}
void dfscalc(int nod)
{
for(int q:muchii[nod])
{
int i=abs(q);
if(i!=par[nod])
{
dfscalc(i);
val[nod]+=val[i];
}
}
if(val[nod])
{
int a=min(nod,par[nod]);
int b=max(nod,par[nod]);
used.push_back(gethash(a,b));
}
comp[nod]=what;
}
void dfsbuild(int nod)
{
val[nod]=0;
dp[0][nod]=par[nod];
int loga=log2(niv[nod])+1;
for(int i=1;i<=loga;i++)
dp[i][nod]=dp[i-1][dp[i-1][nod]];
for(int q:muchii[nod])
{
int i=abs(q);
if(i!=par[nod])
{
par[i]=nod;
niv[i]=niv[nod]+1;
dfsbuild(i);
}
}
}
void dsumerge(int a, int b)
{
int c1=comp[a],c2=comp[b];
if(lg[c1]<lg[c2])
{
swap(a,b);
swap(c1,c2);
}
what=c1;
dfscalc(myroot[c2]);
par[b]=a;
lg[c1]+=lg[c2];
lg[c2]=0;
niv[b]=niv[a]+1;
muchii[a].push_back(b);
muchii[b].push_back(a);
dfsbuild(b);
}
int main()
{
ios_base::sync_with_stdio(false);
cin>>n>>m;
muchii.resize(n+1);
for(int i=1;i<=n;i++)
{
niv[i]=1;
lg[i]=1;
comp[i]=i;
myroot[i]=i;
par[i]=0;
val[i]=0;
}
int cnt=0;
for(int z=1;z<=m;z++)
{
int a,b;
cin>>a>>b;
if(comp[a]!=comp[b])
{
cnt++;
dsumerge(a,b);
}
else
{
int lca=LCA(a,b);
val[a]++;
val[b]++;
val[lca]-=2;
}
}
for(int i=1;i<=n;i++)
if(lg[i])
dfscalc(myroot[i]);
sort(used.begin(),used.end());
used.erase(unique(used.begin(),used.end()),used.end());
int poz=0;
for(int i=1;i<=n;i++)
{
for(int j:muchii[i])
if(j>i)
{
ll h=gethash(i,j);
int st=0;
int dr=used.size();
dr--;
bool ok=1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(h==used[mij])
{
ok=0;
break;
}
if(h>used[mij])
st=mij+1;
else
dr=mij-1;
}
if(ok)
cout<<i<<' '<<j<<'\n';
}
}
return 0;
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:134:9: warning: unused variable 'poz' [-Wunused-variable]
134 | int poz=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
852 KB |
Output is correct |
| 2 |
Correct |
4 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
764 KB |
Output is correct |
| 2 |
Correct |
151 ms |
728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
1440 KB |
Output is correct |
| 2 |
Correct |
359 ms |
1636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
489 ms |
3104 KB |
Output is correct |
| 2 |
Correct |
420 ms |
4036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
711 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
673 ms |
9468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1113 ms |
10156 KB |
Output is correct |
| 2 |
Correct |
1064 ms |
10548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1511 ms |
12248 KB |
Output is correct |
| 2 |
Correct |
1506 ms |
12760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1845 ms |
12248 KB |
Output is correct |
| 2 |
Correct |
1783 ms |
12820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2319 ms |
11792 KB |
Output is correct |
| 2 |
Correct |
2201 ms |
12768 KB |
Output is correct |
