Submission #376290

#	Time	Username	Problem	Language	Result	Execution time	Memory
376290		tqbfjotld	Papričice (COCI20_papricice)	C++14	110 / 110	277 ms	44264 KiB

papricice

#include <bits/stdc++.h>
using namespace std;

int sz[200005];
vector<pair<int,int> > paths[200005];
int big[200005];
int big2[200005];
int hd[200005];
vector<int> adjl[200005];
int pa[200005][20];

void dfs(int node, int p){
    pa[node][0] = p;
    for (int x = 1; x<20; x++){
        pa[node][x] = pa[pa[node][x-1]][x-1];
    }
    sz[node] = 1;
    for (auto x : adjl[node]){
        if (x==p) continue;
        dfs(x,node);
        sz[node] += sz[x];
    }
}
void decomp(int node, int p, int head){
    paths[head].push_back({-sz[node],node});
    hd[node] = head;
    int v1 = 0;
    int v2 = 0;
    big2[node] = -1; big[node] = -1;
    for (auto x : adjl[node]){
        if (x==p) continue;
        if (sz[x]>v1){
            v2 = v1;
            big2[node] = big[node];
            v1 = sz[x]; big[node] = x;
        }
        else if (sz[x]>v2){
            v2 = sz[x];
            big2[node] = x;
        }
    }
    if (big[node]!=-1)decomp(big[node],node,head);
    if (big2[node]!=-1)decomp(big2[node],node,big2[node]);
}
int n;

int getv(int a, int b){
    return max(a,max(b,n-a-b))-min(a,min(b,n-a-b));
}

int check(int node){
    //printf("checking %d\n",node);
    if (hd[node]==1){
        int remsize = n-sz[node];
        int thing = remsize/2;
        if (thing==0){
            return 999999999;
        }
        int tt = lower_bound(paths[hd[node]].begin(),paths[hd[node]].end(),make_pair(-thing-sz[node]+1,-1))-paths[hd[node]].begin();
        int splitnode = paths[hd[node]][tt-1].second;
        //printf("split1 = %d\n",splitnode);
        int t2 = -1;
        if (big2[splitnode]!=-1) t2 = lower_bound(paths[big2[splitnode]].begin(),paths[big2[splitnode]].end(),make_pair(1-thing,-1))-paths[big2[splitnode]].begin();
        if (t2==0) {
            int ans = getv(sz[node],sz[splitnode]-sz[node]);
            if (big[splitnode]!=-1 && big[splitnode]!=node)ans = min(ans,getv(sz[node],sz[big[splitnode]]-sz[node]));
            if (big2[splitnode]!=-1) ans = min(ans,getv(sz[node],sz[big2[splitnode]]));
            return ans;
        }
        if (t2==-1){
            int ans = getv(sz[node],sz[splitnode]-sz[node]);
            if (big[splitnode]!=-1 && big[splitnode]!=node)ans = min(ans,getv(sz[node],sz[big[splitnode]]-sz[node]));
            return ans;
        }
        splitnode = paths[big2[splitnode]][t2-1].second;

        //printf("split2 = %d\n",splitnode);
        int ans = getv(sz[node],sz[splitnode]);
        if (big[splitnode]!=-1) ans = min(ans,getv(sz[node],sz[big[splitnode]]));
        return ans;
    }
    else{
        int remsize = n-sz[node];
        int thing = remsize/2;
        if (thing==0){
            return 999999999;
        }
        int imptnode = node;
        for (int x = 19; x>=0; x--){
            if (pa[imptnode][x]!=0 && hd[pa[imptnode][x]]!=1){
                imptnode = pa[imptnode][x];
            }
        }
        int bef = imptnode;
        imptnode = pa[imptnode][0];
        if (sz[big[imptnode]]>=thing){
            //printf("far main branch\n");
            int t2 = lower_bound(paths[1].begin(),paths[1].end(),make_pair(1-thing,-1))-paths[1].begin();
            int splitnode = paths[1][t2-1].second;
            int ans = getv(sz[node],sz[splitnode]);
            if (big[splitnode]!=-1){
                ans = min(ans,getv(sz[node],sz[big[splitnode]]));
            }
            return ans;
        }
        //printf("near main branch\n");
        int tt = lower_bound(paths[1].begin(),paths[1].end(),make_pair(-thing-sz[node]+1,-1))-paths[1].begin();
        int splitnode = paths[1][tt-1].second;
        int ans = getv(sz[node],sz[splitnode]-sz[node]);
        if (big[splitnode]!=-1) ans = min(ans,getv(sz[node],sz[big[splitnode]]));
        if (bef!=node) ans = min(ans,getv(sz[node],sz[bef]-sz[node]));
        return ans;

    }
}

int main(){
    scanf("%d",&n);
    for (int x = 0; x<n-1; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        adjl[a].push_back(b);
        adjl[b].push_back(a);
    }
    dfs(1,0);
    //printf("dfs done\n");
    decomp(1,0,1);
    //printf("decomp done\n");
    int ans = 999999999;
    for (int x = 1; x<=n; x++){
        ans = min(ans,check(x));
    }
    printf("%d",ans);
}

Compilation message (stderr)

papricice.cpp: In function 'int main()':
papricice.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
papricice.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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