oj.uz

답안 #1111163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111163 2024-11-11T15:34:46 Z Ghulam_Junaid Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 893 ms 81224 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
 
int n, t, m, dp[N], par[N], cnt_child[N];
vector<int> g[N];
 
void dfs(int v, int p = -1){
    int mx = 0;
    int mx2 = 0;
 
    par[v] = p;
    int children = 0;
    for (int u : g[v]){
        if (u == p) continue;
 
        children++;
        dfs(u, v);
 
        mx2 = max(mx2, dp[u]);
        if (mx < mx2)
            swap(mx, mx2);
    }
 
    // cout << "for v = " << v << " : " << children << " " << mx2 << endl;
    cnt_child[v] = children;
    dp[v] = children + mx2;
    // cout << dp[v] << endl;
}
 
int main(){
    cin >> n >> t >> m;
 
    for (int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
 
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    dfs(t);
 
    int cur = m;
    while (par[cur] != -1){
        cur = par[cur];
        dp[m] += cnt_child[cur] - 1;
    }
 
    cout << dp[m] << endl;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 524 ms 80200 KB Output is correct
2 Correct 406 ms 74404 KB Output is correct
3 Correct 870 ms 81224 KB Output is correct
4 Correct 416 ms 52296 KB Output is correct
5 Correct 893 ms 80992 KB Output is correct
6 Correct 813 ms 81224 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 23888 KB Output isn't correct
2 Halted 0 ms 0 KB -