Submission #347074

#	Time	Username	Problem	Language	Result	Execution time	Memory
347074		patrikpavic2	Network (BOI15_net)	C++17	100 / 100	605 ms	85352 KiB

net

#include <cstdio>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;

const int N = 1e6 + 500;

vector < pii > sol;
vector < int > v[N];
int n, root;

vi dfs(int x, int lst){
	if((int)v[x].size() == 1) return {x};
	vi ret;
	for(int y : v[x]){
		if(y == lst) continue;
		vi nxt = dfs(y, x);
		if((int)nxt.size() == 1){
			if((int)ret.size() > 1){
				sol.PB({nxt[0], ret.back()});
				ret.pop_back();
			}
			else
				ret.PB(nxt[0]);
		}
		else{
			if((int)ret.size() > 0){
				sol.PB({nxt[0], ret.back()});
				ret.pop_back();
				ret.PB(nxt[1]);
			}
			else{
				ret.PB(nxt[0]); 
				ret.PB(nxt[1]);
			}
		}
	}
	//printf("x = %d ret = %d\n", x, (int)ret.size());
	if(lst == x){
		if((int)ret.size() == 2)
			sol.PB({ret[0], ret[1]});
		else
			sol.PB({ret[0], x});
	}
	return ret;
}

int main(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	root = 1;
	while((int)v[root].size() == 1) root++;
	dfs(root, root);
	printf("%d\n", (int)sol.size());
	for(pii tmp : sol)
		printf("%d %d\n", tmp.X, tmp.Y);
	return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
net.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

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