Submission #788998

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788998	2023-07-20T20:09:25 Z	lovrot	Computer Network (BOI14_network)	C++17	Compilation error	0 ms	0 KB

network

#include <cstdio>
#include <vector>

#define EB emplace_back

using namespace std;

const int N = 5e5 + 10;

int n;
vector<int> G[N];

vector<int> F[N];

void dfs(int u, int p) {
	if((int) G[u].size() == 1) {
		F[u].EB(u);
		return;
	}
	int xam = 0, cnt = 0, w;
	for(int v : G[u]) {
		if(v == p) continue;
		dfs(v, u); 
		if((int) F[v].size() > xam) {
			xam = F[v].size();
			w = v;
		}
		if((int) F[v].size() > 1) ++cnt;
	}
	int lst = F[w].back();
	F[w].pop_back();
	for(int v : G[u]) { 
		if(v == p || v == w) continue;	
		for(int i = 0; i < (int) F[v].size() - 1; ++i) F[w].EB(F[v][i]);
	}
	if(cnt > 1) F[w].EB(lst);
	for(int v : G[u]) {
		if(v == p || v == w) continue;
		F[w].EB(F[v].back());
	}
	if(cnt <= 1) F[w].EB(lst);
	swap(F[u], F[w]); 
/*	printf("%d : [", u);
	for(int v : F[u]) printf("%d, ", v); 
	printf("]\n");
*/}

int main() {
	scanf("%d", &n);
	int root;
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		scanf("%d%d", &u, &v); 
		G[u].EB(v);
		G[v].EB(u); 
		if(G[u].size() > 1) root = u;
		if(G[v].size() > 1) root = v;
	}
//	printf("root %d\n", root); 
	dfs(root, 0);
	printf("%d\n", (int) (F[root].size() + 1) / 2);
	for(int i = 0; i < F[root].size(); i += 2) {
		if(i == F[root].size() - 1) --i;
		printf("%d %d\n", F[root][i], F[root][i + 1]);
	}
	return 0;
}

Compilation message

network.cpp: In function 'int main()':
network.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 0; i < F[root].size(); i += 2) {
      |                 ~~^~~~~~~~~~~~~~~~
network.cpp:63:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   if(i == F[root].size() - 1) --i;
      |      ~~^~~~~~~~~~~~~~~~~~~~~
network.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
network.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
grader.c: In function 'int main()':
grader.c:48:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf ("%d%d%d%d", &N, &a, &b, &M);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
grader.c:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf("%d", &distance[u][v]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccMatI8D.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cca6MywE.o:network.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccMatI8D.o: in function `main':
grader.c:(.text.startup+0xc9): undefined reference to `findRoute(int, int, int)'
collect2: error: ld returned 1 exit status