oj.uz

답안 #468872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468872 2021-08-30T05:00:20 Z qwerasdfzxcl Papričice (COCI20_papricice) C++14
0 / 110
 9 ms 14412 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), S.lower_bound(n-x*2), S.lower_bound((n-x+1)/2)};
    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), S.upper_bound(n-x*2), S.upper_bound((n-x+1)/2)};
    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]];
    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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Incorrect 9 ms 14412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Incorrect 9 ms 14412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Incorrect 9 ms 14412 KB Output isn't correct
3 Halted 0 ms 0 KB -