oj.uz

Submission #766693

# Submission time Handle Problem Language Result Execution time Memory
766693 2023-06-26T04:32:34 Z Pichon5 Papričice (COCI20_papricice) C++17
50 / 110
 919 ms 22380 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 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=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 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5184 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 5188 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5032 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5184 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 5188 KB Output is correct
11 Correct 772 ms 21652 KB Output is correct
12 Correct 919 ms 21512 KB Output is correct
13 Correct 617 ms 22380 KB Output is correct
14 Incorrect 718 ms 22228 KB Output isn't correct
15 Halted 0 ms 0 KB -