Submission #1011882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011882		Dedibeat	Papričice (COCI20_papricice)	C++17	15 / 110	9 ms	1116 KiB

papricice

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e3 + 5;
vector<int> adj[N + 5];
vector<int> child[N+5];
int sz[N + 5];
void dfs(int v, int last){
     sz[v] = 1;
     child[v].push_back(v);
     for(auto u : adj[v]){
            if(u != last) dfs(u , v);
     }
     for(auto u : adj[v]){
            if(u == last) continue;
            sz[v] += sz[u];
            for(auto it : child[u]){
                   child[v].push_back(it);
            }
     }
 }

int main(){
       int n;
       cin >> n;
       for(int i = 1; i<n; i++){
           int x, y;
           cin >> x >> y;
           adj[x].push_back(y);
           adj[y].push_back(x);
       }
       dfs(1, 1);
       int ans = n;
       for(int i = 2; i<=n; i++){
           // cout << sz[i] << endl;
                bool c[n+5];
                for(int j = 0; j<=n; j++){
                     c[j] = false;
                }
                for(auto u : child[i])  c[u] = true;
                int A, B, C;
                for(int j = 2; j<=n; j++){
                      if(c[j]) C = sz[j], B = sz[i] - sz[j], A = n - sz[i];
                      else C = sz[j], B = sz[i], A = n - sz[i] - sz[j];
                      ans = min(ans, max(abs(A - B), max(abs(A - C), abs(B - C))));
                    //  cout << i << " " << j << " " << A << " " << B << " " << C << endl;
                }
       }
       cout << ans << endl;




}

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