Submission #376312

#	Time	Username	Problem	Language	Result	Execution time	Memory
376312		lyc	Papričice (COCI20_papricice)	C++14	50 / 110	16 ms	4460 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 = 2005;

int N;
vector<int> al[mxN];
int sub[mxN], pa[mxN];
bool isp[mxN][mxN];

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

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

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);
    }

    dfs(1,-1);

    FOR(i,1,N){
        for (int j = pa[i]; j != -1; j = pa[j]) isp[i][j] = 1;
    }

    int ans = mxN;
    FOR(i,1,N){
        FOR(j,i+1,N){
            if (isp[i][j])
                ans = min(ans, calc(sub[i],sub[j]-sub[i],N-sub[j]));
            else if (isp[j][i])
                ans = min(ans, calc(sub[j],sub[i]-sub[j],N-sub[i]));
            else
                ans = min(ans, calc(sub[i],sub[j],N-sub[i]-sub[j]));
        }
    }
    cout << ans << '\n';
}

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