Submission #376686

#	Time	Username	Problem	Language	Result	Execution time	Memory
376686		lyc	Papričice (COCI20_papricice)	C++14	110 / 110	316 ms	28396 KiB

papricice

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 2e5+5;

int N;
vector<int> al[mxN];
int sub[mxN];
multiset<int> done, vis;
int ans;

int subtree(int u, int p) {
    sub[u] = 1;
    for (int& v : al[u]) if (v != p) {
        sub[u] += subtree(v,u);
    }
    return sub[u];
}

int calc(int a, int b, int c) {
    return max({a,b,c}) - min({a,b,c});
}

void dfs(int u, int p) {
    multiset<int>::iterator it;
    // done
    it = done.lower_bound((N-sub[u]+1)/2);
    if (it != done.end()) {
        ans = min(ans, calc(N-*it-sub[u],*it,sub[u]));
    }
    if (it != done.begin()) {
        --it;
        ans = min(ans, calc(N-*it-sub[u],*it,sub[u]));
    }
    // vis
    it = vis.lower_bound((N-sub[u]+1)/2+sub[u]);
    if (it != vis.end()) {
        ans = min(ans, calc(N-*it,*it-sub[u],sub[u]));
    }
    if (it != vis.begin()) {
        --it;
        ans = min(ans, calc(N-*it,*it-sub[u],sub[u]));
    }

    vis.insert(sub[u]);
    for (int& v : al[u]) if (v != p)
        dfs(v,u);

    vis.erase(vis.find(sub[u]));
    done.insert(sub[u]);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N;
    FOR(i,1,N-1){
        int X, Y; cin >> X >> Y;
        al[X].push_back(Y);
        al[Y].push_back(X);
    }

    ans = N;
    subtree(1,0);
    dfs(1,0);
    cout << ans << '\n';
}

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