Submission #894631

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
894631	2023-12-28 14:38:55	IWKR	Factories (JOI14_factories)	C++17	100 / 100	3135 ms	231208 KiB

factories

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
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<pair<int, int>> adjlist[500001];
int subsz[500001], level[500001], centpar[500001][20];
long long dist[500001][20], ans[500001];
vector<int> v;
void dfs(int x, int p) {
    subsz[x] = 1;
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs(i.first, x);
        subsz[x] += subsz[i.first];
    }
}
int centroid(int x, int p, int treesz) {
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        if (treesz < subsz[i.first] * 2) {
            return centroid(i.first, x, treesz);
        }
    }
    return x;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67