Submission #711678

#	Time	Username	Problem	Language	Result	Execution time	Memory
711678		Pherokung	Network (BOI15_net)	C++14	100 / 100	472 ms	65396 KiB

net

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define pb push_back
#define F first
#define S second
typedef pair<int,int> pa;
int n,u,v,top;
vector<int> adj[MAXN];
vector<pa> ans;

pa merge(pa A, pa B){
	if(A == make_pair(-1,-1)) return B;
	if(B == make_pair(-1,-1)) return A;
	if(A.S == - 1 && B.S == -1) return {A.F,B.F};
	if(A.S != -1 && B.S != -1){
		ans.push_back({A.S,B.S});
		return {A.F,B.F};
	}
	if(A.S != -1){
		ans.push_back({A.S,B.F});
		return {A.F,-1};
	}
	if(B.S != -1){
		ans.push_back({B.S,A.F});
		return {B.F,-1};
	}
}

pa dfs(int u,int p){
	pa val = (adj[u][0] == p && adj[u].size() == 1) ? make_pair(u,-1) : make_pair(-1,-1);
	for(auto v : adj[u]){
		if(v == p) continue;
		val = merge(val,dfs(v,u));
	}
	//printf("!! %d : %d %d\n",u,val.F,val.S);
	return val;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		adj[u].pb(v), adj[v].pb(u);
	}
	
	for(int i=1;i<=n;i++) if(adj[i].size() > 1) top = i;
	pa val = dfs(top,top);
	if(val.F != -1 && val.S != -1) ans.push_back({val.F,val.S});
	else if(val.F != -1) ans.push_back({val.F,top});
	
	printf("%d\n",ans.size());
	for(auto x : ans) printf("%d %d\n",x.F,x.S);
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:52: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=]
   52 |  printf("%d\n",ans.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<std::pair<int, int> >::size_type {aka long unsigned int}
      |          %ld
net.cpp: In function 'pa merge(pa, pa)':
net.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^
net.cpp: In function 'int main()':
net.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
net.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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