#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fastmath")
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,int poz)
{
val[nod]=0;
dp[0][nod]=par[nod];
int loga=log2(niv[nod])+1;
for(int i=max(1,poz);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;
int prvniv=niv[i];
niv[i]=niv[nod]+1;
dfsbuild(i,log2(prvniv)-1);
}
}
}
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,0);
}
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:4:32: warning: bad option '-ffastmath' to pragma 'optimize' [-Wpragmas]
4 | #pragma GCC optimize("fastmath")
| ^
pipes.cpp:13:20: warning: bad option '-ffastmath' to attribute 'optimize' [-Wattributes]
13 | int LCA(int a,int b)
| ^
pipes.cpp:36:24: warning: bad option '-ffastmath' to attribute 'optimize' [-Wattributes]
36 | int gethash(int a,int b)
| ^
pipes.cpp:44:21: warning: bad option '-ffastmath' to attribute 'optimize' [-Wattributes]
44 | void dfscalc(int nod)
| ^
pipes.cpp:63:30: warning: bad option '-ffastmath' to attribute 'optimize' [-Wattributes]
63 | void dfsbuild(int nod,int poz)
| ^
pipes.cpp:82:27: warning: bad option '-ffastmath' to attribute 'optimize' [-Wattributes]
82 | void dsumerge(int a, int b)
| ^
pipes.cpp:100:10: warning: bad option '-ffastmath' to attribute 'optimize' [-Wattributes]
100 | int main()
| ^
pipes.cpp: In function 'int main()':
pipes.cpp:137:9: warning: unused variable 'poz' [-Wunused-variable]
137 | int poz=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
852 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
852 KB |
Output is correct |
| 2 |
Incorrect |
166 ms |
748 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
1440 KB |
Output is correct |
| 2 |
Incorrect |
327 ms |
1536 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
514 ms |
3108 KB |
Output is correct |
| 2 |
Correct |
430 ms |
3912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
704 ms |
9028 KB |
Output is correct |
| 2 |
Incorrect |
753 ms |
9412 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1239 ms |
10156 KB |
Output is correct |
| 2 |
Correct |
1071 ms |
10416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1642 ms |
12244 KB |
Output is correct |
| 2 |
Incorrect |
1575 ms |
12688 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2140 ms |
12248 KB |
Output is correct |
| 2 |
Incorrect |
1901 ms |
12840 KB |
Wrong number of edges |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2393 ms |
11692 KB |
Output is correct |
| 2 |
Correct |
2270 ms |
12660 KB |
Output is correct |
