oj.uz

Submission #931643

# Submission time Handle Problem Language Result Execution time Memory
931643 2024-02-22T07:40:48 Z vjudge1 Network (BOI15_net) C++17
18 / 100
 2000 ms 75192 KB 
#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 = 500'000 + 5, LG = 20, 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.count() == leaves) break;
		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

net.cpp: In function 'int main()':
net.cpp:96:19: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |   if(mark.count() == leaves) break;
      |      ~~~~~~~~~~~~~^~~~~~~~~
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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49756 KB Output is correct
2 Correct 7 ms 49780 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Correct 7 ms 49756 KB Output is correct
5 Correct 7 ms 49752 KB Output is correct
6 Correct 7 ms 49756 KB Output is correct
7 Correct 7 ms 49756 KB Output is correct
8 Correct 7 ms 49756 KB Output is correct
9 Correct 7 ms 49752 KB Output is correct
10 Correct 7 ms 49756 KB Output is correct
11 Correct 7 ms 49756 KB Output is correct
12 Correct 7 ms 49760 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49752 KB Output is correct
15 Correct 7 ms 49756 KB Output is correct
16 Correct 7 ms 49696 KB Output is correct
17 Correct 7 ms 49756 KB Output is correct
18 Correct 8 ms 49756 KB Output is correct
19 Correct 8 ms 49708 KB Output is correct
20 Correct 7 ms 49756 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49756 KB Output is correct
2 Correct 7 ms 49780 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Correct 7 ms 49756 KB Output is correct
5 Correct 7 ms 49752 KB Output is correct
6 Correct 7 ms 49756 KB Output is correct
7 Correct 7 ms 49756 KB Output is correct
8 Correct 7 ms 49756 KB Output is correct
9 Correct 7 ms 49752 KB Output is correct
10 Correct 7 ms 49756 KB Output is correct
11 Correct 7 ms 49756 KB Output is correct
12 Correct 7 ms 49760 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49752 KB Output is correct
15 Correct 7 ms 49756 KB Output is correct
16 Correct 7 ms 49696 KB Output is correct
17 Correct 7 ms 49756 KB Output is correct
18 Correct 8 ms 49756 KB Output is correct
19 Correct 8 ms 49708 KB Output is correct
20 Correct 7 ms 49756 KB Output is correct
21 Correct 7 ms 49756 KB Output is correct
22 Execution timed out 2036 ms 75192 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 49756 KB Output is correct
2 Correct 7 ms 49780 KB Output is correct
3 Correct 8 ms 49756 KB Output is correct
4 Correct 7 ms 49756 KB Output is correct
5 Correct 7 ms 49752 KB Output is correct
6 Correct 7 ms 49756 KB Output is correct
7 Correct 7 ms 49756 KB Output is correct
8 Correct 7 ms 49756 KB Output is correct
9 Correct 7 ms 49752 KB Output is correct
10 Correct 7 ms 49756 KB Output is correct
11 Correct 7 ms 49756 KB Output is correct
12 Correct 7 ms 49760 KB Output is correct
13 Correct 7 ms 49756 KB Output is correct
14 Correct 7 ms 49752 KB Output is correct
15 Correct 7 ms 49756 KB Output is correct
16 Correct 7 ms 49696 KB Output is correct
17 Correct 7 ms 49756 KB Output is correct
18 Correct 8 ms 49756 KB Output is correct
19 Correct 8 ms 49708 KB Output is correct
20 Correct 7 ms 49756 KB Output is correct
21 Correct 7 ms 49756 KB Output is correct
22 Execution timed out 2036 ms 75192 KB Time limit exceeded
23 Halted 0 ms 0 KB -