Submission #448161

#	Time	Username	Problem	Language	Result	Execution time	Memory
448161		jk410	Papričice (COCI20_papricice)	C++17	0 / 110	1 ms	372 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int N,Ans=INF;
int Size[2001];
vector<int> Edge[2001];
vector<pair<int,int>> Edge_List;
void dfs(int v,int par){
    Size[v]=1;
    for (int i:Edge[v]){
        if (i==par)
            continue;
        dfs(i,v);
        Size[v]+=Size[i];
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N;
    for (int i=1; i<N; i++){
        int a,b;
        cin>>a>>b;
        Edge[a].push_back(b);
        Edge[b].push_back(a);
        Edge_List.push_back({a,b});
    }
    for (auto i:Edge_List){
        for (int i=1; i<=N; i++)
            Size[i]=0;
        dfs(i.second,i.first);
        for (int j=1; j<=N; j++){
            if (!Size[j]||j==i.second)
                continue;
            Ans=min(Ans,max({Size[j],Size[i.second]-Size[j],N-Size[i.second]})-min({Size[j],Size[i.second]-Size[j],N-Size[i.second]}));
        }
    }
    cout<<Ans;
    return 0;
}

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