oj.uz

Submission #766695

# Submission time Handle Problem Language Result Execution time Memory
766695 2023-06-26T04:34:32 Z Pichon5 Papričice (COCI20_papricice) C++17
50 / 110
 968 ms 22180 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) {
	return (int) ( (((double) rand() / RAND_MAX) * (mod) ));
}
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 3 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 4948 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 3 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 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 6 ms 5168 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 7 ms 5076 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 6 ms 5168 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 7 ms 5076 KB Output is correct
11 Correct 806 ms 21660 KB Output is correct
12 Correct 947 ms 21508 KB Output is correct
13 Correct 591 ms 22180 KB Output is correct
14 Correct 761 ms 21876 KB Output is correct
15 Incorrect 968 ms 21796 KB Output isn't correct
16 Halted 0 ms 0 KB -