Submission #605754

#	Time	Username	Problem	Language	Result	Execution time	Memory
605754		aSSSd	Network (BOI15_net)	C++14	0 / 100	1 ms	316 KiB

net

//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);
	}
}
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);
		}
	}
	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 (stderr)

net.cpp: In function 'int main()':
net.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i + 1 < pos.size(); i +=2){
      |                 ~~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37