oj.uz

Submission #851594

# Submission time Handle Problem Language Result Execution time Memory
851594 2023-09-20T07:56:30 Z dosts Papričice (COCI20_papricice) C++17
110 / 110
 984 ms 28384 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 5724 KB Output is correct
2 Correct 2 ms 5720 KB Output is correct
3 Correct 2 ms 5720 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5720 KB Output is correct
3 Correct 2 ms 5720 KB Output is correct
4 Correct 2 ms 5720 KB Output is correct
5 Correct 2 ms 5720 KB Output is correct
6 Correct 4 ms 5720 KB Output is correct
7 Correct 4 ms 5720 KB Output is correct
8 Correct 4 ms 5720 KB Output is correct
9 Correct 4 ms 5720 KB Output is correct
10 Correct 4 ms 5724 KB Output is correct
11 Correct 846 ms 21788 KB Output is correct
12 Correct 984 ms 21644 KB Output is correct
13 Correct 591 ms 24604 KB Output is correct
14 Correct 642 ms 24264 KB Output is correct
15 Correct 774 ms 24400 KB Output is correct
16 Correct 439 ms 24132 KB Output is correct
17 Correct 840 ms 24076 KB Output is correct
18 Correct 614 ms 28384 KB Output is correct
19 Correct 690 ms 24144 KB Output is correct
20 Correct 856 ms 24176 KB Output is correct