oj.uz

Submission #765709

# Submission time Handle Problem Language Result Execution time Memory
765709 2023-06-25T03:35:54 Z vjudge1 Network (BOI15_net) C++17
0 / 100
 6 ms 12060 KB 
// Problem: C - Интернет связь
// Contest: Virtual Judge - IOI contest div-B
// URL: https://vjudge.net/contest/564767#problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(v) (v).begin(),(v).end()
#define rall(v) ((v).rbegin()), ((v).rend())
#define out(v)  for(auto& i : v) cout << i << ' ';
#define F first
#define S second
#define int long long

const ll N = 5e5 + 17;
const ll MOD = 1e9 + 7;
const string alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

vector <int > g[N] , ans;
int cnt = 1;

void dfs(int v , int pr = -1){
	if (g[v].size() == 1){
		ans.pb(v);
	}
	for(auto to : g[v]){
		if (pr != to){
			dfs(to , v);
		}
	}
}

void solve (){
	int n;
	cin >>n;
	for(int i = 1; i <= n - 1; i ++){
		int x , y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	vector <int > lst;
	dfs(1);
	// for(auto to : ans){
		// cout <<to << " ";
	// }
	// cout << endl;
	vector <int > c1 , c2;
	for(int i = 0; i < ans.size(); i ++){
		if ((i + 1) <= ans.size() / 2){
			c1.pb(ans[i]);
		}
		else {
			c2.pb(ans[i]);
		}
	}
	cout <<(ans.size() + 1) / 2 << endl;
	if (ans.size() % 2 == 0){
		for(int i = 0; i < c1.size(); i ++){
			cout <<c1[i] << " " << c2[i] << endl;
		}
	}
	else {
		for(int i = 0; i < c1.size(); i ++){
			cout <<c1[i] << " " << c2[i] << endl;
		}
		cout <<c2[c2.size() - 1] << " " << c1[1] << endl;
	}
}

signed main(){
	// freopen("ones.in" , "r" , stdin) ;
	// freopen("ones.out" , "w" , stdout) ;
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	// int cs = 1;
	// cin >>T;
	while (T --){
		// cout <<"Case " << cs ++<< ":" << endl;
		solve ();
		// cout <<endl;
	}
}

Compilation message

net.cpp: In function 'void solve()':
net.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i < ans.size(); i ++){
      |                 ~~^~~~~~~~~~~~
net.cpp:57:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if ((i + 1) <= ans.size() / 2){
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~
net.cpp:66:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i = 0; i < c1.size(); i ++){
      |                  ~~^~~~~~~~~~~
net.cpp:71:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i = 0; i < c1.size(); i ++){
      |                  ~~^~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 5 ms 12060 KB Integer 0 violates the range [1, 10]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 5 ms 12060 KB Integer 0 violates the range [1, 10]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 5 ms 12060 KB Integer 0 violates the range [1, 10]
5 Halted 0 ms 0 KB -