#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<vector<int>> muchii;
vector<int> comp,myroot,dp[17],val,par,niv,lg;
unordered_map<int,bool> 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[gethash(a,b)]=1;
}
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);
comp.resize(n+1);
lg.resize(n+1);
for(int i=0;i<17;i++)
dp[i].resize(n+1);
val.resize(n+1);
par.resize(n+1);
niv.resize(n+1);
myroot.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);
if(used.count(h)==0)
cout<<i<<' '<<j<<'\n';
}
}
return 0;
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:142:9: warning: unused variable 'poz' [-Wunused-variable]
142 | int poz=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
956 KB |
Output is correct |
| 2 |
Correct |
172 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
1996 KB |
Output is correct |
| 2 |
Correct |
320 ms |
2108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
472 ms |
4888 KB |
Output is correct |
| 2 |
Correct |
396 ms |
5812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
747 ms |
13344 KB |
Output is correct |
| 2 |
Correct |
653 ms |
13212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1145 ms |
15116 KB |
Output is correct |
| 2 |
Correct |
1113 ms |
14964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1568 ms |
19332 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1974 ms |
19340 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2354 ms |
18588 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
