Submission #468879

#	Time	Username	Problem	Language	Result	Execution time	Memory
468879		qwerasdfzxcl	Papričice (COCI20_papricice)	C++14	110 / 110	505 ms	82408 KiB

papricice

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[200200];
multiset<int> st[200200];
int sz[200200], num[200200], n, ans = 1e9, cnt;

void dfs0(int s, int pa = -1){
    sz[s] = 1;
    for (auto &v:adj[s]) if (pa!=v){
        dfs0(v, s);
        sz[s] += sz[v];
    }
}

void calc2(int x, int y){
    //printf("%d %d\n", x, y);
    ans = min(ans, max({x, y, n-x-y})-min({x, y, n-x-y}));
}

void calc(int x, multiset<int> &S, int t){
    if (S.empty()) return;
    auto iter = S.lower_bound((n-x+1)/2+t);
    if (iter!=S.end()) calc2(x, *iter-t);
    if (iter!=S.begin()) calc2(x, *(--iter)-t);
}

void _move(int x, int y){
    for (auto &z:st[x]) st[y].insert(z);
}

multiset<int> cur;
void dfs(int s, int pa = -1){
    if (pa!=-1){
        calc(sz[s], cur, sz[s]);
        cur.insert(sz[s]);
    }

    if (adj[s].size()==1 && pa!=-1){
        st[cnt].insert(1);
        num[s] = cnt;
        cnt++;
        cur.erase(cur.find(1));
        return;
    }
    for (auto &v:adj[s]) if (v!=pa){
        if (sz[v]>sz[adj[s][0]] || adj[s][0]==pa) swap(v, adj[s][0]);
    }
    for (auto &v:adj[s]) if (v!=pa) dfs(v, s);
    for (int i=1;i<(int)adj[s].size();i++) if (adj[s][i]!=pa){
        for (auto &x:st[num[adj[s][i]]]) calc(x, st[num[adj[s][0]]], 0);
        _move(num[adj[s][i]], num[adj[s][0]]);
    }
    st[num[adj[s][0]]].insert(sz[s]);
    num[s] = num[adj[s][0]];
    /*printf("%d %d: ", s, adj[s][0]);
    for (auto &x:st[num[s]]) printf("%d ", x);
    printf("\n");*/
    if (pa!=-1) cur.erase(cur.find(sz[s]));
}

int main(){
    scanf("%d", &n);
    for (int i=0;i<n-1;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs0(1);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
papricice.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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