Submission #1248328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248328		dfhdfhdsf	Papričice (COCI20_papricice)	C++20	15 / 110	2 ms	836 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 1e9;
int n;
vector<vector<int>> adj, children;
vector<int> tin, tout, euler, sz;
int timer;
vector<int> B;                   
vector<vector<int>> bests;     
int ans;

void dfs1(int u, int p){
    sz[u] = 1;
    tin[u] = ++timer;
    euler[timer] = u;
    for(int v: adj[u]){
        if(v==p) continue;
        children[u].push_back(v);
        dfs1(v,u);
        sz[u] += sz[v];
    }
    tout[u] = timer;
}

void forward_scan(){
    multiset<int> st;
    vector<vector<int>> nodesAtTin(n+1);
    for(int u=2; u<=n; u++){
        nodesAtTin[tin[u]].push_back(u);
    }
    for(int i=1; i<=n; i++){
        for(int u: nodesAtTin[i]){
            int r = n - sz[u];
            int target = r/2;
            if(!st.empty()){
                auto it = st.lower_bound(target);
                if(it!=st.end()) bests[u].push_back(*it);
                if(it!=st.begin()){
                    --it;
                    bests[u].push_back(*it);
                }
            }
        }
        st.insert(B[i]);
    }
}

void backward_scan(){
    multiset<int> st;
    vector<vector<int>> nodesAtTout(n+2);
    for(int u=2; u<=n; u++){
        nodesAtTout[tout[u]].push_back(u);
    }
    for(int i=n; i>=1; i--){
        for(int u: nodesAtTout[i]){
            int r = n - sz[u];
            int target = r/2;
            if(!st.empty()){
                auto it = st.lower_bound(target);
                if(it!=st.end()) bests[u].push_back(*it);
                if(it!=st.begin()){
                    --it;
                    bests[u].push_back(*it);
                }
            }
        }
        st.insert(B[i]);
    }
}

set<int>* dfs_dsu(int u){
    auto *S = new set<int>();
    S->insert(sz[u]);
    for(int v: children[u]){
        auto *Sv = dfs_dsu(v);
        if(S->size() < Sv->size()) swap(S, Sv);
        for(int x: *Sv) S->insert(x);
        delete Sv;
    }
    int s = sz[u];
    int r = n - s;
    int target = s/2;
    if(!S->empty()){
        auto it = S->lower_bound(target);
        vector<int> cands;
        if(it!=S->end()) cands.push_back(*it);
        if(it!=S->begin()){
            --it;
            cands.push_back(*it);
        }
        for(int a: cands){
            int b = s - a;
            int mx = max({a,b,r});
            int mn = min({a,b,r});
            ans = min(ans, mx - mn);
        }
    }
    for(int a: bests[u]){
        int b = (n - s) - a;
        int c = s;
        int mx = max({a,b,c});
        int mn = min({a,b,c});
        ans = min(ans, mx - mn);
    }
    return S;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    adj.assign(n+1,{});
    children.assign(n+1,{});
    tin.assign(n+1,0);
    tout.assign(n+1,0);
    euler.assign(n+1,0);
    sz.assign(n+1,0);
    B.assign(n+1,0);
    bests.assign(n+1,{}); 
    timer = 0;

    for(int i=1,x,y;i<n;i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs1(1,0);
    for(int i=1;i<=n;i++){
        B[i] = sz[euler[i]];
    }
    forward_scan();
    backward_scan();

    ans = n;
    auto *unused = dfs_dsu(1);
    delete unused;

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60