Submission #388670

#	Time	Username	Problem	Language	Result	Execution time	Memory
388670		phathnv	Papričice (COCI20_papricice)	C++11	110 / 110	376 ms	28388 KiB

papricice

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Papricice"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 2e5 + 1;

int n;
vector <int> adj[N];
int sz[N], res = N;
multiset <int> szPar, szChild;

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

void dfs1(int u, int p){
    sz[u] = 1;
    for(int v : adj[u]){
        if (v == p)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p){
    int best = (n - sz[u]) / 2;
    auto it = szChild.upper_bound(best);
    if (it != szChild.end()){
        int minSz = min(sz[u], min(*it, n - sz[u] - *it));
        int maxSz = max(sz[u], max(*it, n - sz[u] - *it));
        res = min(res, maxSz - minSz);
    }
    if (it != szChild.begin()){
        --it;
        int minSz = min(sz[u], min(*it, n - sz[u] - *it));
        int maxSz = max(sz[u], max(*it, n - sz[u] - *it));
        res = min(res, maxSz - minSz);
    }

    best += sz[u];
    it = szPar.upper_bound(best);
    if (it != szPar.end()){
        int minSz = min(sz[u], min(*it - sz[u], n - *it));
        int maxSz = max(sz[u], max(*it - sz[u], n - *it));
        res = min(res, maxSz - minSz);
    }
    if (it != szPar.begin()){
        --it;
        int minSz = min(sz[u], min(*it - sz[u], n - *it));
        int maxSz = max(sz[u], max(*it - sz[u], n - *it));
        res = min(res, maxSz - minSz);
    }

    szPar.insert(sz[u]);
    for(int v : adj[u]){
        if (v == p)
            continue;
        dfs2(v, u);
    }
    szChild.insert(sz[u]);
    szPar.erase(szPar.find(sz[u]));
}

void solve(){
    dfs1(1, -1);
    dfs2(1, -1);
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    solve();
    return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   87 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   88 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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