Submission #1156593

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1156593	2025-02-24 10:45:17	beaconmc	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	1880 ms	41304 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// not my code - I write better code than this
#include <bits/stdc++.h>
using namespace std;
const int X = 500;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, K;
  cin >> N >> K;
  /*
    for each node u, the answer is:
    - let the number of people on the i-th layer in the tree liking language l be b_li
    - let the number of people on the i-th layer in the subtree of u be a_ui
    - let the number of people in the subtree of u liking language L[u] be c_u
    - ans[u][0] = sum of min(a_ui, b_li) for all i
    - ans[u][1] = ans[0] - c_u
  */
  /*
    for each language:
    - if number who prefer >= X:
      -> at most N/X of these
      -> run O(N log N) small to large algorithm
      -> algorithm O(N log N * (N/X))
    - if number who prefer < X
      -> run O(X^2 log N) algorithm
      -> so altogether is O(N/X * X^2 log N) = O(NX log N)
    - so want N*N*logN/X = N*X*logN => N=X*X => X=sqrt(N) = 320
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 12 / 12
• Subtask 2: 19 / 19
• Subtask 3: 27 / 27
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19