Submission #1168164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168164		Ghulam_Junaid	새로운 문제 (POI13_luk)	C++20	100 / 100	432 ms	26504 KiB

luk

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

const int N = 3e5 + 100;
int n, dp[N], X;
vector<int> g[N];

void dfs(int v, int p = -1){
    int ch = 0, sm = 0;
    for (int u : g[v]){
        if (u == p) continue;
        ch++;
        dfs(u, v);
        sm += dp[u];
    }
    dp[v] = max(0, ch - X + sm);
}

int main(){
    cin >> n;
    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int l = -1;
    int r = n;
    while (r - l > 1){
        int mid = (l + r) / 2;
        X = mid;
        dfs(1);
        if (dp[1] > 0) l = mid;
        else r = mid;
    }
    cout << r << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10