oj.uz

Submission #766678

# Submission time Handle Problem Language Result Execution time Memory
766678 2023-06-26T04:13:34 Z Pichon5 Papričice (COCI20_papricice) C++17
50 / 110
 990 ms 28024 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
const int tam=200005;
vi G[tam];
int sz[tam];
multiset<int> todos;
int res=1e9;
void init(int nodo, int ant){
    sz[nodo]=1;
    for(auto x:G[nodo]){
        if(x!=ant){
            init(x,nodo);
            sz[nodo]+=sz[x];
        }
    }
}
int n;
void dfs(int nodo, int ant){
    for(auto it : G[nodo]){
        if(it==ant)continue;
        int tami=sz[it];
        int falta=n-tami;
        auto it2=todos.lower_bound((n-sz[it])/2);
        if(it2!=todos.end()){
            int val=(*it2);
            int ahora=max({val,falta-val,tami})-min({val,falta-val,tami});
            res=min(res,ahora);
        }
        if(it2!=todos.begin()){
            it2--;
            int val=(*it2);
            int ahora=max({val,falta-val,tami})-min({val,falta-val,tami});
            res=min(res,ahora);
        }
        dfs(it,nodo);
    }
    
    if(ant!=-1){
        todos.insert(sz[nodo]);
    }
}
int main(){
    fast
    int a,b;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        G[a].pb(b);
        G[b].pb(a);
    }
    for(int i=1;i<=9;i++){
        todos.clear();
        int cual=rand()%n+1;
        init(cual,-1);
        dfs(cual,-1);
    }
    cout<<res<<"\n";

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 5 ms 5076 KB Output is correct
11 Correct 874 ms 21720 KB Output is correct
12 Correct 990 ms 21516 KB Output is correct
13 Correct 733 ms 22180 KB Output is correct
14 Correct 749 ms 21808 KB Output is correct
15 Correct 912 ms 24024 KB Output is correct
16 Correct 453 ms 23972 KB Output is correct
17 Correct 813 ms 24224 KB Output is correct
18 Correct 741 ms 28024 KB Output is correct
19 Incorrect 756 ms 24272 KB Output isn't correct
20 Halted 0 ms 0 KB -