제출 #1094646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094646		stefanneagu	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	743 ms	77888 KiB

mousetrap

#include <bits/stdc++.h>
#define int long long 
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;
}

int32_t 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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35