Submission #931638

#	Time	Username	Problem	Language	Result	Execution time	Memory
931638		vjudge1	Network (BOI15_net)	C++17	18 / 100	2064 ms	68576 KiB

net

#include<bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define pb              push_back
#define F               first
#define S               second
#define len(x)          (int)x.size()
#define all(x)          x.begin(),x.end()
#define file            freopen("matrix.txt", "r", stdin);freopen("a.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; continue;}
//#define int             long long

const int maxn = 300'000 + 5, LG = 31, MOD = 1e9+7;// 998244353
const ll inf =  1061109567;

//priority_queue< pii , vector<pii> , greater<pii> pq;

int n, d[maxn], par[LG][maxn];
vector<int> g[maxn];
bitset<maxn> mark;

void dfs(int v = 1, int p = 0) {

	for(int i = 1; i < LG; ++i) 
		par[i][v] = par[i-1][par[i-1][v]];

	for(int u : g[v]) 
		if(u ^ p) {
			par[0][u] = v;
			d[u] = d[v] + 1;
			dfs(u, v);
		}

}

int lca(int v, int u) {
    if(v == u) return v;
 
    if(d[v] < d[u]) swap(u, v);
 
    int distance = d[v] - d[u];
    for(int i = 0; i < LG; ++i)
        if(distance & (1 << i)) v = par[i][v];
 
    if(u == v) return v;
 
    while(u != v) {
        int l = 0, r = LG;
        while(r-l > 1) {
            int mid = (r+l) / 2;
            if(par[mid][u] == par[mid][v]) r = mid;
            else l = mid;
        }
        u = par[l][u], v = par[l][v];
    }
 
    return v;
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);	
	
	cin >> n;
	for(int i = 0; i < n-1; ++i) {
		int v, u;
		cin >> v >> u;
		g[v].pb(u); g[u].pb(v);
	}

	dfs();
	vector<int> l;
	for(int i = 1; i <= n; ++i) if(len(g[i]) == 1) l.pb(i);
	int leaves = len(l);
	vector<pair<int, pii>> v;
	
	for(int i = 0; i < leaves; ++i) {
		for(int j = i+1; j < leaves; ++j) {
			int LCA = lca(l[i], l[j]);
			v.pb({d[l[i]] + d[l[j]] - 2 * d[LCA], {l[i], l[j]}});
		}
	}

	sort(all(v));
	reverse(all(v));

	cout << (leaves + 1)/2 << '\n';

	for(int i = 0; i < len(v); ++i) {
		int vv = v[i].S.F, u = v[i].S.S;
		if(!mark[vv] && !mark[u]) {
			cout << vv << ' ' << u << '\n';
			mark[vv] = mark[u] = 1;
		}
		else {
			if(leaves % 2 == 0) continue;
			else
				if(mark.count() == leaves - 1) {
					if(!mark[vv]) {
						cout << vv << ' ' << v[0].S.F << '\n';
						break;
					}
					else if(!mark[u]){
						cout << u << ' ' << v[0].S.F << '\n';
						break;
					}

				}
		}
	}
	
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:104:21: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |     if(mark.count() == leaves - 1) {
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~

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