Submission #59626

#	Time	Username	Problem	Language	Result	Execution time	Memory
59626		IvanC	Network (BOI15_net)	C++17	0 / 100	15 ms	12132 KiB

net

#include <bits/stdc++.h>
using namespace std;

typedef tuple<int,int,int> trinca;
typedef pair<int,int> ii;

const int MAXN = 5*1e5 + 10;

vector<int> grafo[MAXN];
vector<ii> pares;
int seg[4*MAXN],nivel[MAXN],vetor[MAXN],ini[MAXN],fim[MAXN],raiz,dfsCount,N;

inline int join(int a,int b){
	return (a != 0) ? (a) : (b);
}

void build(int pos,int left,int right){
	if(left == right){
		seg[pos] = vetor[left];
		return;
	}
	int mid = (left+right)/2;
	build(2*pos,left,mid);
	build(2*pos+1,mid+1,right);
	seg[pos] = join(seg[2*pos],seg[2*pos+1]);
}

void update(int pos,int left,int right,int x){
	if(left == right){
		seg[pos] = 0;
		vetor[left] = 0;
		return;
	}
	int mid = (left+right)/2;
	if(x <= mid) update(2*pos,left,mid,x);
	else update(2*pos+1,mid+1,right,x);
	seg[pos] = join(seg[2*pos],seg[2*pos+1]);
}

int query(int pos,int left,int right,int i,int j){
	if(left >= i && right <= j) return seg[pos];
	int mid = (left+right)/2;
	if(j <= mid) return query(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query(2*pos+1,mid+1,right,i,j);
	else return join( query(2*pos,left,mid,i,j),query(2*pos+1,mid+1,right,i,j));
}

void dfs1(int v,int p){
	ini[v] = ++dfsCount;
	for(int u : grafo[v]){
		if(u == p) continue;
		nivel[u] = nivel[v] + 1;
		dfs1(u,v);
	}
	fim[v] = dfsCount;
	if(ini[v] == fim[v]) vetor[ini[v]] = v; 
	//printf("V %d Ini %d Fim %d\n",v,ini[v],fim[v]);
}

void dfs2(int v,int p){

	priority_queue<trinca> pq;

	for(int u : grafo[v]){
		if(u == p) continue;
		//printf("Filho %d Pai %d\n",u,v);
		int k = query(1,1,N,ini[u],fim[u]);
		if(k == 0) continue;
		pq.push(make_tuple(nivel[k],k,u));
		//printf("Folha %d Sub %d\n",k,u);
	}

	while(pq.size() >= 2){
		trinca folha1 = pq.top();
		pq.pop();
		trinca folha2 = pq.top();
		pq.pop();
		int f1 = get<1>(folha1), f2 = get<1>(folha2), r = get<2>(folha1),s = get<2>(folha2);
		pares.push_back(ii(f1,f2));
		update(1,1,N,ini[f1]);
		update(1,1,N,ini[f2]);
		int k1 = query(1,1,N,ini[r],fim[r]);
		if(k1 != 0) pq.push(make_tuple(nivel[k1],k1,r));
		int k2 = query(1,1,N,ini[s],fim[s]);
		if(k2 != 0) pq.push(make_tuple(nivel[k2],k2,s));
		//printf("F1 %d F2 %d K1 %d K2 %d\n",f1,f2,k1,k2);
	}

	if(pq.size() == 1){
		dfs2(get<2>(pq.top()),v);
	}
	else{
		return;
	}

}

int main(){

	scanf("%d",&N);
	for(int i = 1;i<N;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	raiz = 1;
	for(int i = 1;i<=N;i++){
		if(grafo[i].size() >= 2){
			raiz = i;
			break;
		}
	}

	dfs1(raiz,-1);
	build(1,1,N);
	dfs2(raiz,-1);

	//printf("Raiz %d Exemplo %d\n",raiz, query(1,1,N,ini[raiz],fim[raiz]) );
	//printf("%d\n",(int)pares.size());
	//for(ii aresta : pares) printf("%d %d\n",aresta.first,aresta.second);
	//printf("#############\n");

	for(int i = 1;i<=N;i++){
		if(vetor[i] != 0){
			pares.push_back(ii(vetor[i],raiz));
		}
	}

	printf("%d\n",(int)pares.size());
	for(ii aresta : pares) printf("%d %d\n",aresta.first,aresta.second);

	return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
net.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

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