oj.uz

Submission #1094645

# Submission time Handle Problem Language Result Execution time Memory
1094645 2024-09-30T07:58:14 Z stefanneagu Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 730 ms 73296 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e6 + 1;

int dp[nmax];

vector<int> adj[nmax];

void dfs(int i, int tata = 0) {
	int minn = 1e9;
	for(auto it : adj[i]) {
		if(it == tata) {
			continue;
		}
		dfs(it, i);
		minn = min(minn, dp[it]);
	}
	if(adj[i].size() == 1) {
		dp[i] = 0;
		return;
	}
	dp[i] = minn + adj[i].size() - 1;
}

int main() {
	int n, ep, sp;
	cin >> n >> ep >> sp;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(ep);
	cout << dp[sp];
  return 0;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 72276 KB Output is correct
2 Correct 422 ms 67412 KB Output is correct
3 Incorrect 730 ms 73296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 35.0

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