oj.uz

Submission #468873

# Submission time Handle Problem Language Result Execution time Memory
468873 2021-08-30T05:08:40 Z qwerasdfzxcl Papričice (COCI20_papricice) C++14
110 / 110
 669 ms 84804 KB 
#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;
    calc2(x, *S.begin()-t);
    calc2(x, *S.rbegin()-t);
    multiset<int>::iterator iter[] = {S.lower_bound(x+t), S.lower_bound(n-x*2+t), S.lower_bound((n-x+1)/2+t)};
    for (int i=0;i<3;i++) if (iter[i]!=S.end()) calc2(x, *iter[i]-t);
    multiset<int>::iterator iter2[] = {S.upper_bound(x+t), S.upper_bound(n-x*2+t), S.upper_bound((n-x+1)/2+t)};
    for (int i=0;i<3;i++) if (iter2[i]!=S.begin()) calc2(x, *(--iter2[i])-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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 12 ms 14796 KB Output is correct
7 Correct 12 ms 14796 KB Output is correct
8 Correct 11 ms 14796 KB Output is correct
9 Correct 11 ms 14788 KB Output is correct
10 Correct 12 ms 14796 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 8 ms 14404 KB Output is correct
5 Correct 8 ms 14412 KB Output is correct
6 Correct 12 ms 14796 KB Output is correct
7 Correct 12 ms 14796 KB Output is correct
8 Correct 11 ms 14796 KB Output is correct
9 Correct 11 ms 14788 KB Output is correct
10 Correct 12 ms 14796 KB Output is correct
11 Correct 598 ms 75248 KB Output is correct
12 Correct 669 ms 78768 KB Output is correct
13 Correct 482 ms 69640 KB Output is correct
14 Correct 540 ms 74004 KB Output is correct
15 Correct 668 ms 81732 KB Output is correct
16 Correct 378 ms 49792 KB Output is correct
17 Correct 546 ms 71276 KB Output is correct
18 Correct 455 ms 50292 KB Output is correct
19 Correct 633 ms 84804 KB Output is correct
20 Correct 604 ms 75076 KB Output is correct