oj.uz

Submission #1016147

# Submission time Handle Problem Language Result Execution time Memory
1016147 2024-07-07T12:46:15 Z vjudge1 Papričice (COCI20_papricice) C++17
110 / 110
 175 ms 23376 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5888 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5888 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 4 ms 5208 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 4 ms 5768 KB Output is correct
9 Correct 5 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5888 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 4 ms 5208 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 4 ms 5768 KB Output is correct
9 Correct 5 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 129 ms 14652 KB Output is correct
12 Correct 175 ms 14672 KB Output is correct
13 Correct 148 ms 15076 KB Output is correct
14 Correct 115 ms 14788 KB Output is correct
15 Correct 149 ms 14676 KB Output is correct
16 Correct 130 ms 14564 KB Output is correct
17 Correct 143 ms 14808 KB Output is correct
18 Correct 174 ms 23376 KB Output is correct
19 Correct 118 ms 14708 KB Output is correct
20 Correct 127 ms 14676 KB Output is correct