| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 910836 |
2024-01-18T08:24:43 Z |
asdasdqwer |
Pipes (CEOI15_pipes) |
C++14 |
|
807 ms |
18596 KB |
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p,r;
DSU(int n) : p(n),r(n,1) {
for (int i=0;i<n;i++)p[i]=i;
}
int get(int i) {
if (p[i]!=i && p[i]!=p[p[i]]) p[i]=get(p[i]);
return p[i];
}
bool unite(int a,int b) {
a=get(a),b=get(b);
if (a==b)return false;
if (r[a]<r[b])swap(a,b);
p[b]=a;
r[a]+=r[b];
return true;
}
};
vector<int> st(1e5+1, 0);
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;cin>>n>>m;
DSU d1(n), d2(n);
vector<vector<int>> g(n);
for (int i=0;i<m;i++) {
int a,b;cin>>a>>b;a--;b--;
if (d1.unite(a,b)) {
g[a].push_back(b);
g[b].push_back(a);
}
else {
d2.unite(a,b);
}
}
d1.r.clear();
d2.r.clear();
vector<vector<int>> lft(n, vector<int>(18, -1));
bitset<100001> vis;
vector<int> d(n,0);
for (int i=0;i<n;i++) {
if (vis[i]) continue;
int pt=0;
st[pt]=i;
vis[i]=true;
while (pt != -1) {
int r=st[pt--];
for (int x:g[r]) {
if (!vis[x]) {
vis[x]=true;
lft[x][0]=r;
d[x]=d[r]+1;
st[++pt]=x;
}
}
}
}
for (int j=1;j<18;j++) {
for (int i=0;i<n;i++) {
lft[i][j]=lft[i][j-1];
if (lft[i][j] != -1) {
lft[i][j]=lft[lft[i][j]][j-1];
}
}
}
vector<int> dp(n, 0);
for (int i=0;i<n;i++) {
if (d2.p[i] == i) continue;
int a=i, b=d2.get(i);
dp[a]++;
dp[b]++;
if (d[a]<d[b])swap(a,b);
int steps=d[a]-d[b];
int cnt=0;
while (steps) {
if ((steps&1)==1) {
a=lft[a][cnt];
}
steps>>=1;cnt++;
}
if (a==b) {
dp[a]-=2;
continue;
}
for (int i=17;i>-1;--i) {
if (lft[a][i] != lft[b][i]) {
a=lft[a][i];
b=lft[b][i];
}
}
dp[lft[a][0]] -= 2;
}
d.clear();
for (int i=0;i<n;i++) {
lft[i]={lft[i][0]};
}
for (int i=0;i<n;i++) vis[i]=0;
for (int i=0;i<n;i++) {
st[i]=-1;
}
for (int i=0;i<n;i++) {
if (vis[i])continue;
int pt=0;
vis[i]=true;
st[0]=i;
while (pt != -1) {
int r=st[pt];
if (g[r].size()==0) {
if (lft[r][0] != -1) {
dp[lft[r][0]] += dp[r];
}
pt--;
continue;
}
for (int x:g[r]) {
if (!vis[x]) {
st[++pt]=x;
vis[x]=true;
}
}
g[r].clear();
}
}
st.clear();
for (int i=0;i<n;i++) {
if (dp[i]==0 && lft[i][0] != -1) {
cout<<i+1<<" "<<lft[i][0]+1<<"\n";
}
}
dp.clear();
lft.clear();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
860 KB |
Output is correct |
| 2 |
Correct |
1 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
1360 KB |
Output is correct |
| 2 |
Correct |
64 ms |
1340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
2388 KB |
Output is correct |
| 2 |
Correct |
143 ms |
2528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
5084 KB |
Output is correct |
| 2 |
Correct |
171 ms |
5908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
285 ms |
13388 KB |
Output is correct |
| 2 |
Correct |
243 ms |
13136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
466 ms |
15232 KB |
Output is correct |
| 2 |
Correct |
433 ms |
15012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
705 ms |
18592 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
679 ms |
18596 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
807 ms |
17732 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
