Submission #59622

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59622	2018-07-22T18:34:51 Z	IvanC	Network (BOI15_net)	C++17	0 / 100	13 ms	12136 KB

net

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

typedef pair<int,int> ii;

const int MAXN = 5*1e5 + 10;

vector<int> grafo[MAXN];
vector<ii> pares;
int seg[3*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;
		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){

	stack<ii> pilha;

	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;
		pilha.push(ii(k,u));
		//printf("Folha %d Sub %d\n",k,u);
	}

	while(pilha.size() >= 2){
		ii folha1 = pilha.top();
		pilha.pop();
		ii folha2 = pilha.top();
		pilha.pop();
		int f1 = folha1.first, f2 = folha2.first, r = folha1.second,s = folha2.second;
		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) pilha.push(ii(k1,r));
		int k2 = query(1,1,N,ini[s],fim[s]);
		if(k2 != 0) pilha.push(ii(k2,s));
		//printf("F1 %d F2 %d K1 %d K2 %d\n",f1,f2,k1,k2);
	}

	if(pilha.size() == 1){
		dfs2(pilha.top().second,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

net.cpp: In function 'int main()':
net.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
net.cpp:101: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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12024 KB	Output is correct
2	Incorrect	13 ms	12136 KB	Breaking single line is causing network to disconnect.
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12024 KB	Output is correct
2	Incorrect	13 ms	12136 KB	Breaking single line is causing network to disconnect.
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	12024 KB	Output is correct
2	Incorrect	13 ms	12136 KB	Breaking single line is causing network to disconnect.
3	Halted	0 ms	0 KB	-