제출 #1337410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1337410		hauserl	Mousetrap (CEOI17_mousetrap)	C++20	25 / 100	675 ms	86652 KiB

mousetrap

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n,t,m; 

vector<vector<ll>> adj;
vector<ll> countSubtrees;
vector<ll> dp;
vector<ll> parent;
vector<bool> onMainPath;
vector<ll> mainPath;

// void dfsDp(int u, int p) {
    

//     ll max1 = 0;
//     ll max2 = 0;

//     for (const auto& v : adj[u]) {
//         if (v == p) continue;
//         dfsDp(v, u);

//         if (dp[v] > max1) {
//             max2 = max1;
//             max1 = dp[v];
//         } else if (dp[v] > max2) {
//             max2 = dp[v];
//         }
//     } 

//     // dp
//     if (adj[u].size() == 1) dp[u] = 0;
//     else dp[u] = max2 + adj[u].size() - 2 + 1;
// }

void dfsDp(int u, int p) {
    

    vector<ll> children;
    for (const auto& v : adj[u]) {
        if (v == p) continue;
        dfsDp(v, u);
        children.push_back(dp[v]);
    } 

    sort(children.rbegin(), children.rend());
    
    if (children.empty()) dp[u] = 0;
    else if (children.size() == 1) dp[u] = 1;
    else dp[u] = children[1] + children.size();
}

bool findPath(int u, int p) {
    parent[u] = p;
    if (u == m) {
        mainPath.push_back(u);
        return onMainPath[u] = true;
    }
    for (const auto& v : adj[u]) {
        if (v == p) continue;
        if (findPath(v, u)) {
            mainPath.push_back(u);
            return onMainPath[u] = true;
        }
    }
    return false;
}

bool checkMid(ll x) {
    ll moves = 0;
    ll blocks = 0;
    for (ll i = 0; i < mainPath.size()-1; i++) {
        int u = mainPath[i];
        int brToB = 0;

        if (u == t) break;

        int sideBr = adj[u].size() - 2;
        if (u == m) sideBr++;

        blocks += sideBr;
        
        for (const auto& v : adj[u]) {
            if (onMainPath[v] || v == parent[u]) continue;
            if (dp[v] + countSubtrees[u] > x) brToB++;
        }

        moves += brToB;

        if (moves > i + 1) return false;
    }

    return moves <= x;
}

int main() {

    scanf("%lld %lld %lld",&n,&t,&m);
    adj.resize(n+1, vector<ll>());
    countSubtrees.resize(n+1, 0);
    dp.resize(n+1, -1);
    parent.resize(n+1, -1);
    onMainPath.resize(n+1, false);

    for (int i = 1; i < n; i++) {
        ll a,b; scanf("%lld %lld",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    findPath(t, -1);

    dfsDp(t, -1);

    // subtrees
    for (int i = mainPath.size() -1; i >= 0; i--) {
        ll u = mainPath[i];
        ll tN = adj[u].size();
        if (u == m) countSubtrees[u] = tN - 1 + countSubtrees[parent[u]];
        else if (u == t) countSubtrees[u] = 0;
        else countSubtrees[u] = tN - 2 + countSubtrees[parent[u]];
    }
    



    ll l = -1;
    ll r = n +1;

    while (l + 1 < r) {
        ll mid = l + (r-l)/2;

        if (checkMid(mid)) r = mid;
        else l = mid;
    }

    printf("%lld", r);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%lld %lld %lld",&n,&t,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:107:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         ll a,b; scanf("%lld %lld",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35