Submission #1168095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168095		Sir_Ahmed_Imran	Triumphal arch (POI13_luk)	C++20	100 / 100	369 ms	23728 KiB

luk

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 300001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int dp[N];
int dept[N];
vector<int> a[N];

void dfs(int v, int u, int x){
    dp[v] = a[v].size() - 1;
    for(auto & i : a[v])
        if(i != u) dfs(i, v, x);
    if(dp[v] > x) 
        dp[u] += dp[v] - x;
}

void solve(){
    int n, p, q;
    cin >> n;
    a[1].append(0);
    for(int i = 1; i < n; i++){
        cin >> p >> q;
        a[p].append(q);
        a[q].append(p);
    }
    int ans = -1;
    for(int i = 262144; i > 0; i /= 2){
        dp[0] = 0;
        dfs(1, 0, ans + i);
        if(dp[0]) ans += i;
    }
    cout << ans + 1;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

• 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