oj.uz

Submission #468879

# Submission time Handle Problem Language Result Execution time Memory
468879 2021-08-30T05:21:33 Z qwerasdfzxcl Papričice (COCI20_papricice) C++14
110 / 110
 505 ms 82408 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;
    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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14388 KB Output is correct
3 Correct 9 ms 14380 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14360 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 14388 KB Output is correct
3 Correct 9 ms 14380 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14360 KB Output is correct
6 Correct 10 ms 14800 KB Output is correct
7 Correct 11 ms 14796 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 10 ms 14796 KB Output is correct
10 Correct 11 ms 14788 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 14388 KB Output is correct
3 Correct 9 ms 14380 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14360 KB Output is correct
6 Correct 10 ms 14800 KB Output is correct
7 Correct 11 ms 14796 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 10 ms 14796 KB Output is correct
10 Correct 11 ms 14788 KB Output is correct
11 Correct 505 ms 72832 KB Output is correct
12 Correct 466 ms 76304 KB Output is correct
13 Correct 351 ms 67428 KB Output is correct
14 Correct 377 ms 71416 KB Output is correct
15 Correct 460 ms 79096 KB Output is correct
16 Correct 256 ms 48064 KB Output is correct
17 Correct 378 ms 68908 KB Output is correct
18 Correct 342 ms 47624 KB Output is correct
19 Correct 441 ms 82408 KB Output is correct
20 Correct 423 ms 72516 KB Output is correct