| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605756 |
2022-07-26T01:38:38 Z |
aSSSd |
Network (BOI15_net) |
C++14 |
|
1 ms |
212 KB |
//ANh Ok
#include<bits/stdc++.h>
#define forin(i,a,b) for(int i = a; i <= b; i ++)
#define forde(i,a,b) for(int i = a; i >= b; i --)
#define forv(a,b) for(auto & a : b)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
vector<vector<pii> > ke;
vector<int> num,low,id,vis;
vector<vector<int> > twin;
stack<int> st;
int cnt , Time;
void dfs(int u, int pre){
num[u] = low[u] = ++Time;
vis[u] = 1;
st.push(u);
forv(e,ke[u]){
int v = e.fi;
int p = e.se;
if(p!=pre){
if(vis[v] == 0){
dfs(v,p);
low[u] = min(low[u],low[v]);
}
else low[u] = min(low[u],num[v]);
}
}
if(low[u] == num[u]){
++cnt;
int v;
do{
v = st.top();
st.pop();
id[v] = cnt;
twin[cnt].push_back(v);
}while(v!=u);
}
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n,m; cin >> n;
m=n-1;
ke.resize(n+1);
forin(i,1,m){
int x,y; cin >> x >> y;
ke[x].push_back(pii(y,i));
ke[y].push_back(pii(x,i));
}
num.resize(n+1,0);
low.resize(n+1,0);
vis.resize(n+1,0);
twin.resize(n+1);
id.resize(n+1,0);
cnt = 0,Time = 0;
forin(i,1,n) if(vis[i]==0) dfs(i,0);
vector<int> pos;
forin(i,1,n){
if(ke[i].size() == 1){
pos.push_back(i);
}
}
shuffle(pos.begin(), pos.end(), rng);
vector<pii> ans;
for(int i = 0; i + 1 < pos.size(); i +=2){
ans.push_back(pii(pos[i],pos[i+1]));
}
if(pos.size() & 1){
ans.push_back(pii(pos.back(),1));
}
cout << ans.size();
cout << "\n";
forv(i,ans) cout << i.fi << " " << i.se << "\n";
}
Compilation message
net.cpp: In function 'int main()':
net.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0; i + 1 < pos.size(); i +=2){
| ~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
