Submission #295648

#	Time	Username	Problem	Language	Result	Execution time	Memory
295648		Plurm	Network (BOI15_net)	C++11	100 / 100	625 ms	124280 KiB

net

#include <bits/stdc++.h>
using namespace std;
vector<int> g[500005];
int dp1[500005];
int dp2[500005];
vector<pair<int,int> > out;
void dfs(int u, int p = -1){
	int chcnt = 0;
	int fch = -1;
	int sch = -1;
	for(int v : g[u]){
		if(v == p) continue;
		if(fch == -1) fch = v;
		else if(sch == -1) sch = v;
		dfs(v, u);
		if(dp1[v] != -1) chcnt++;
		if(dp2[v] != -1) chcnt++;
	}
	if(fch == -1){
		dp1[u] = u;
		dp2[u] = -1;
	}else if(sch == -1){
		dp1[u] = dp1[fch];
		dp2[u] = dp2[fch];
	}else{
		vector<int> sup, gen;
		for(int v : g[u]){
			if(v == p) continue;
			if(dp2[v] == -1) sup.push_back(v);
			else gen.push_back(v);
		}
		if(sup.empty()){
			out.emplace_back(dp2[fch], dp2[sch]);
			dp2[fch] = -1;
			dp2[sch] = -1;
			gen.clear();
			for(int v : g[u]){
				if(v == p) continue;
				if(dp2[v] == -1) sup.push_back(v);
				else gen.push_back(v);
			}
		}
		if(gen.size() == 1){
			if(sup.size() >= 1){
				out.emplace_back(dp2[gen.back()], dp1[sup.back()]);
				dp2[gen.back()] = -1;
				sup.pop_back();
				sup.push_back(gen.back());
				gen.pop_back();
			}else{
				printf("Invalid case\n");
			}
		}
		for(int i = 0; i < gen.size(); i++){
			out.emplace_back(dp1[gen[i]], dp2[gen[(i+1) % gen.size()]]);
		}
		for(int i = 0; i < (int)sup.size()-2; i += 2){
			out.emplace_back(dp1[sup[i]], dp1[sup[i+1]]);
		}
		if(sup.size() % 2 == 1){
			dp1[u] = dp1[sup.back()];
			dp2[u] = -1;
		}else{
			dp1[u] = dp1[sup[sup.size()-1]];
			dp2[u] = dp1[sup[sup.size()-2]];
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i < n; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int root = 1;
	for(int i = 2; i <= n; i++){
		if(g[i].size() > 1) root = i;
	}
	dfs(root);
	if(dp2[root] != -1){
		out.emplace_back(dp1[root], dp2[root]);
	}else{
		out.emplace_back(dp1[root], root);
	}
	printf("%d\n",out.size());
	for(auto p : out){
		printf("%d %d\n",p.first,p.second);
	}
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int, int)':
net.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i < gen.size(); i++){
      |                  ~~^~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:88:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
   88 |  printf("%d\n",out.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |          %ld
net.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
net.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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