Submission #883720

#	Time	Username	Problem	Language	Result	Execution time	Memory
883720		HossamHero7	Papričice (COCI20_papricice)	C++14	0 / 110	2 ms	5724 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 2e5 + 5;
int n;
vector<int> adj[N];
int subtree[N];
vector<int> path;
void calc(int node,int par){
    subtree[node] = 1;
    for(auto ch : adj[node]){
        if(ch == par) continue;
        calc(ch,node);
        subtree[node] += subtree[ch];
    }
}
int ans = 1e9;
void dfs1(int node,int par){
    if(node != 1) path.push_back(subtree[node]);
    int a = n , c = subtree[node];
    if(path.size() >= 2){
        int idx = (int)path.size() - 1 - (upper_bound(path.rbegin(),path.rend(),2*c) - path.rbegin() - 1);
        if(idx >= 0 && idx < path.size()-1 && path[idx] >= (a + c + 1) / 2) ans = min(ans , c - (a - path[idx]));
        idx = (int)path.size() - 1 - (lower_bound(path.rbegin(),path.rend(),2*c) - path.rbegin());
        if(idx < path.size()-1 && path[idx] <= (a + c) / 2) ans = min(ans , a - path[idx] - c);
        idx = (int)path.size() - 1 -(lower_bound(path.rbegin(),path.rend(),max(a-c,2*c)) - path.rbegin());
        if(idx < path.size()-1) ans = min(ans , path[idx] - c - (a - path[idx]));
        idx = (int)path.size() - 1 - (upper_bound(path.rbegin(),path.rend(),min(a-c,2*c)) - path.rbegin() - 1);
        if(idx < path.size()-1) ans = min(ans , a - 2*path[idx] + c);
        idx = (int)path.size() - 1 - (upper_bound(path.rbegin(),path.rend(),(a + c) / 2) - path.rbegin() - 1);
        if(idx >= 0 && idx < path.size()-1 && path[idx] >= a - c) ans = min(ans , 2 * c - path[idx]);
        idx = (int)path.size() - 1 - (lower_bound(path.rbegin(),path.rend(),(a + c + 1) / 2) - path.rbegin());
        if(idx < path.size()-1 && path[idx] <= a - c) ans = min(ans , path[idx] - 2*c);
    }
    for(auto ch : adj[node]){
        if(ch == par) continue;
        dfs1(ch,node);
    }
    if(node != 1) path.pop_back();
}
multiset<int> st;
void dfs2(int node,int par){
    int a = n;
    int c = subtree[node];
    if(st.size()){
        auto it = st.upper_bound((a - c) / 2);
        if(it != st.begin() && (*(--it)) >= c) ans = min(ans , a - (*it) - 2*c);
        it = st.lower_bound((a + c + 1) / 2);
        if(it != st.end() && (*it) <= c) ans = min(ans , 2*c + (*it) - a);
        it = st.upper_bound(min(c,a-2*c));
        if(it != st.begin()) ans = min(ans , a - 2*(*(--it)) - c);
        it = st.lower_bound(max(c,a-2*c));
        if(it != st.end()) ans = min(ans , 2*(*it) + c - a);
        it = st.upper_bound((a - c) / 2);
        if(it != st.begin() && (*(--it)) >= a - 2*c) ans = min(ans , c - (*it));
        it = st.lower_bound((a - c + 1) / 2);
        if(it != st.end() && (*it) <= a - 2*c) ans = min(ans , (*it) - c);
    }
    for(auto ch : adj[node]){
        if(ch == par) continue;
        dfs2(ch,node);
    }
    st.insert(subtree[node]);
}
void solve(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    calc(1,0);
    dfs1(1,0);
    dfs2(1,0);
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'void dfs1(int, int)':
papricice.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if(idx >= 0 && idx < path.size()-1 && path[idx] >= (a + c + 1) / 2) ans = min(ans , c - (a - path[idx]));
      |                        ~~~~^~~~~~~~~~~~~~~
papricice.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(idx < path.size()-1 && path[idx] <= (a + c) / 2) ans = min(ans , a - path[idx] - c);
      |            ~~~~^~~~~~~~~~~~~~~
papricice.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if(idx < path.size()-1) ans = min(ans , path[idx] - c - (a - path[idx]));
      |            ~~~~^~~~~~~~~~~~~~~
papricice.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if(idx < path.size()-1) ans = min(ans , a - 2*path[idx] + c);
      |            ~~~~^~~~~~~~~~~~~~~
papricice.cpp:32:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(idx >= 0 && idx < path.size()-1 && path[idx] >= a - c) ans = min(ans , 2 * c - path[idx]);
      |                        ~~~~^~~~~~~~~~~~~~~
papricice.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if(idx < path.size()-1 && path[idx] <= a - c) ans = min(ans , path[idx] - 2*c);
      |            ~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60