oj.uz

Submission #610547

# Submission time Handle Problem Language Result Execution time Memory
610547 2022-07-28T09:50:52 Z Arnch Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 804 ms 79692 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int n, t, m, total;
bool mark[N];
ll dp[N], par[N], ps[N];
vector<int> adj[N];

void dfs(int x, int p = 0) {
	par[x] = p;

	if(x != t) {
		ps[x] = ps[p] + max(0, Sz(adj[x]) - 2);
	}

	int tim = 0;
	vector<ll> vc;
	for(auto j : adj[x]) {
		if(j == p) continue;
		tim++;
		dfs(j, x);
		vc.push_back(dp[j]);
	}

	sort(All(vc), greater<int>());
	
	if(tim == 0) {
		dp[x] = 0;
		return;
	}
	if(tim == 1) {
		dp[x] = 1;
		return;
	}

	dp[x] = tim;
	dp[x] += vc[1];
}

ll solve(int x) {
	vector<ll> vc;
	for(auto j : adj[x]) {
		if(mark[j] || j == par[x]) continue;
		vc.push_back(dp[j]);
	}
	sort(All(vc), greater<int>());

	ll cnt = ps[par[x]];
	cnt += Sz(vc);

	if(Sz(vc) >= total + 1) cnt += vc[total];
	
	return cnt;
}


int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	cin >>n >>t >>m;
	for(int i = 0; i < n - 1; i++) {
		int u, v; cin >>u >>v;
		adj[u].push_back(v), adj[v].push_back(u);
	}

	dfs(t);

	if(t == m) {
		cout<<0;
		return 0;
	}

	total = 1;
	ll ans = solve(m);

	mark[m] = 1;
	
	int x = par[m];
 
	while(x != t && x != 0) {
		total++;
		ans = max(ans, solve(x));

		mark[x] = 1;
		x = par[x];
	}
 
	cout<<ans;
 
	

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23704 KB Output is correct
2 Correct 14 ms 23736 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 16 ms 23828 KB Output is correct
5 Correct 13 ms 23832 KB Output is correct
6 Correct 13 ms 23820 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 12 ms 23724 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23936 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 78556 KB Output is correct
2 Correct 277 ms 73108 KB Output is correct
3 Correct 749 ms 79684 KB Output is correct
4 Correct 367 ms 51764 KB Output is correct
5 Correct 769 ms 79692 KB Output is correct
6 Correct 804 ms 79684 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23704 KB Output is correct
2 Correct 14 ms 23736 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 16 ms 23828 KB Output is correct
5 Correct 13 ms 23832 KB Output is correct
6 Correct 13 ms 23820 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 12 ms 23724 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23936 KB Output is correct
11 Incorrect 13 ms 23764 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23704 KB Output is correct
2 Correct 14 ms 23736 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 16 ms 23828 KB Output is correct
5 Correct 13 ms 23832 KB Output is correct
6 Correct 13 ms 23820 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 12 ms 23724 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 12 ms 23936 KB Output is correct
11 Correct 335 ms 78556 KB Output is correct
12 Correct 277 ms 73108 KB Output is correct
13 Correct 749 ms 79684 KB Output is correct
14 Correct 367 ms 51764 KB Output is correct
15 Correct 769 ms 79692 KB Output is correct
16 Correct 804 ms 79684 KB Output is correct
17 Incorrect 13 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -