oj.uz

Submission #584943

# Submission time Handle Problem Language Result Execution time Memory
584943 2022-06-28T07:21:45 Z amunduzbaev Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 827 ms 86412 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int long long

const int N = 1e6 + 5;
vector<int> edges[N];
int n, t, m, dp[N], is[N];
int c[N];

void dfs(int u, int p = -1){
	is[u] = (u == t), c[u] = -1;
	vector<int> t;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		is[u] |= is[x];
		if(!is[x]) t.push_back(x);
		else c[u] = x;
	}
	sort(t.begin(), t.end(), [&](int& i, int& j){
		return dp[i] > dp[j];
	});
	edges[u] = t;
	
	if(t.empty()) dp[u] = 0;
	else {
		dp[u] = t.size();
		if((int)t.size() > 1) dp[u] += dp[t[1]]; 
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>t>>m;
	if(t == m){
		cout<<0<<"\n";
		return 0;
	}
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	dfs(m);
	int pos = 0, res = 0;
	while(m != t){
		pos++;
		vector<int>& t = edges[m];
		if(pos >= (int)t.size()){
			pos -= (int)t.size();
			res += (int)t.size();
		} else {
			res += dp[t[pos]] + (int)t.size();
			pos = 1e9;
		}
		m = c[m];
	}
	
	cout<<res<<"\n";
}

/*

8 7 1
1 2
2 3
3 4
3 5
3 6
4 7
4 8

*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 14 ms 23828 KB Output is correct
4 Correct 14 ms 23700 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 13 ms 23808 KB Output is correct
10 Correct 14 ms 23760 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 86412 KB Output is correct
2 Correct 287 ms 80144 KB Output is correct
3 Correct 812 ms 84816 KB Output is correct
4 Correct 406 ms 54256 KB Output is correct
5 Correct 795 ms 84780 KB Output is correct
6 Correct 827 ms 84880 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 14 ms 23828 KB Output is correct
4 Correct 14 ms 23700 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 13 ms 23808 KB Output is correct
10 Correct 14 ms 23760 KB Output is correct
11 Incorrect 12 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 14 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 14 ms 23828 KB Output is correct
4 Correct 14 ms 23700 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 13 ms 23808 KB Output is correct
10 Correct 14 ms 23760 KB Output is correct
11 Correct 372 ms 86412 KB Output is correct
12 Correct 287 ms 80144 KB Output is correct
13 Correct 812 ms 84816 KB Output is correct
14 Correct 406 ms 54256 KB Output is correct
15 Correct 795 ms 84780 KB Output is correct
16 Correct 827 ms 84880 KB Output is correct
17 Incorrect 12 ms 23764 KB Output isn't correct
18 Halted 0 ms 0 KB -