oj.uz

Submission #445967

# Submission time Handle Problem Language Result Execution time Memory
445967 2021-07-20T09:42:02 Z minoum Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 1340 ms 127188 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e6+10;

int n, st, e, p[MAXN], pid[MAXN], dp[MAXN], ans[MAXN], sz[MAXN], cnt[MAXN], ans2[MAXN], bns2[MAXN];
bool mark[MAXN], stuck[MAXN];
vector <pair<int,int>> adj[MAXN];
vector <pair<int,int>> ch[MAXN];

inline void dfs(int v, int parv){
	sz[v] = 1;
	for(auto i: adj[v]){
		if(i.first==parv) continue;
		p[i.first] = v;
		pid[i.first] = i.second;
		dfs(i.first, v);
		sz[v] += sz[i.first];
	}
	return;
}

inline void dfs1(int v, int parv){
	for(auto i: adj[v]){
		int u = i.first, id = i.second;
		if(u==parv) continue;
		if(!mark[id]) cnt[v]++;
		dfs1(u,v);
		ch[v].push_back({dp[u],u});
		if(mark[id]) ans[v] += ans[u];
	}
	if(cnt[v]==0){
		dp[v] = 0; return;
	}
	int mx1 = 0, mx2 = 0;
	for(auto i: adj[v]){
		int u = i.first, id = i.second;
		if(u==parv || mark[id]) continue;
		if(dp[u]>mx1) mx2 = mx1, mx1 = dp[u];
		else if(dp[u]>mx2) mx2 = dp[u];
	}
	dp[v] = 1+mx2+(cnt[v]>1?cnt[v]-1:0); ans[v]+=dp[v];
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> st >> e; st--; e--;
	for(int i = 0; i < n-1; i++){
		int u,v;
		cin >> u >> v; u--; v--;
		adj[u].push_back({v,i});
		adj[v].push_back({u,i});
	}
	dfs(st,-1);
	int u = e;
	while(u!=st){
		mark[pid[u]] = true;
		u = p[u];
	}
	dfs1(st,-1);
	cout << ans[st] << endl;
	return 0; 
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 47300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 121824 KB Output is correct
2 Correct 418 ms 114408 KB Output is correct
3 Correct 1270 ms 127116 KB Output is correct
4 Correct 591 ms 87296 KB Output is correct
5 Correct 1295 ms 127096 KB Output is correct
6 Correct 1340 ms 127188 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 47300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 47300 KB Output isn't correct
2 Halted 0 ms 0 KB -