oj.uz

Submission #468876

# Submission time Handle Problem Language Result Execution time Memory
468876 2021-08-30T05:16:23 Z qwerasdfzxcl Papričice (COCI20_papricice) C++14
110 / 110
 521 ms 82580 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=2;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=2;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 14380 KB Output is correct
2 Correct 8 ms 14352 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14372 KB Output is correct

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14380 KB Output is correct
2 Correct 8 ms 14352 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 8 ms 14372 KB Output is correct
6 Correct 11 ms 14796 KB Output is correct
7 Correct 11 ms 14796 KB Output is correct
8 Correct 10 ms 14788 KB Output is correct
9 Correct 12 ms 14796 KB Output is correct
10 Correct 13 ms 14764 KB Output is correct
11 Correct 464 ms 73000 KB Output is correct
12 Correct 500 ms 76252 KB Output is correct
13 Correct 403 ms 67476 KB Output is correct
14 Correct 421 ms 71528 KB Output is correct
15 Correct 521 ms 79096 KB Output is correct
16 Correct 291 ms 48064 KB Output is correct
17 Correct 433 ms 68708 KB Output is correct
18 Correct 324 ms 47556 KB Output is correct
19 Correct 461 ms 82580 KB Output is correct
20 Correct 451 ms 72516 KB Output is correct