Submission #1016147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016147		vjudge1	Papričice (COCI20_papricice)	C++17	110 / 110	175 ms	23376 KiB

papricice

#include<bits/stdc++.h>

using namespace std;

const int N = 200'000 + 50;
vector<int> G[N];
int n, ans, sz[N];
set<int> s, sp;

void dfs(int v, int p = 0)
{
  sz[v] = 1;
  for(int u : G[v])
    if(p != u)
      dfs(u, v), sz[v] += sz[u];
}

void update(int x, int y, int z)
{
  ans = min(ans, max(x, max(y, z)) - min(x, min(y, z)));
}

void dfs2(int v, int p = 0)
{
  s.insert(sz[v]);

  for(int u : G[v])
    {
      if(p == u) continue;

      int v1 = sz[u] + (n - sz[u]) / 2;
      int v2 = (n - sz[u]) / 2;
      
      auto it = s.upper_bound(v1);

      if(it != s.end())
	update(sz[u], *it - sz[u], n - *it);

      if(it != s.begin())
	{
	  it--;
	  update(sz[u], *it - sz[u], n - *it);
	}

      it = sp.upper_bound(v2);
      if(it != sp.end())
	update(sz[u], *it, n - sz[u] - *it);

      if(it != sp.begin())
	{
	  --it;
	  update(sz[u], *it, n - sz[u] - *it);
	}

      dfs2(u, v);
      
    }
  
  s.erase(sz[v]);
  sp.insert(sz[v]);
}

int main()
{
  cin >> n;
  ans = n;
  
  for(int i = 1; i < n; i++)
    {
      int u, v;
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
    }

  dfs(1);
  dfs2(1);

  cout << ans << endl;
  return 0;
}

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