oj.uz

Submission #766699

# Submission time Handle Problem Language Result Execution time Memory
766699 2023-06-26T04:36:08 Z Pichon5 Papričice (COCI20_papricice) C++17
110 / 110
 900 ms 25892 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 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;
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,tune=native")
#pragma GCC optimize(3)
#pragma GCC optimize("O3")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
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;
        auto it2=todos.lower_bound((n-sz[it])/2);
        if(it2!=todos.end()){
            int val=(*it2);
            int ahora=max({val,n-sz[it]-val,sz[it]})-min({val,n-sz[it]-val,sz[it]});
            res=min(res,ahora);
        }
        if(it2!=todos.begin()){
            it2--;
            int val=(*it2);
            int ahora=max({val,n-sz[it]-val,sz[it]})-min({val,n-sz[it]-val,sz[it]});
            res=min(res,ahora);
        }

        dfs(it,nodo);
    }
    
    if(ant!=-1){
        todos.insert(sz[nodo]);
    }
}

int myrand(int mod) {
    int t = rand() % mod;
    t = (1LL*t*RAND_MAX + rand()) % mod;
    return t;
}
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<=8;i++){
        todos.clear();
        int cual=myrand(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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 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 5 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
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 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 5 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 854 ms 21708 KB Output is correct
12 Correct 890 ms 21516 KB Output is correct
13 Correct 601 ms 22412 KB Output is correct
14 Correct 787 ms 22092 KB Output is correct
15 Correct 900 ms 21536 KB Output is correct
16 Correct 472 ms 22560 KB Output is correct
17 Correct 742 ms 21916 KB Output is correct
18 Correct 670 ms 25892 KB Output is correct
19 Correct 747 ms 21924 KB Output is correct
20 Correct 796 ms 24004 KB Output is correct