Submission #947513

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
947513	2024-03-16 10:24:55	weakweakweak	Capital City (JOI20_capital_city)	C++17	100 / 100	499 ms	57052 KiB

capital_city

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>
using namespace std;
const int N = 510000;
int n, k, col[N], sz[N], parr[N], vis[N] = {0}, ans = INT_MAX, ins[N] = {0}, tt = 3, tt2 = 5;
bool block[N] = {0}, finish[N] = {0};
vector <int> e[N], bel[N];
int dfs_sz (int i, int par) {
    sz[i] = 1;
    parr[i] = par;
    for (int j : e[i]) if (j != par and !block[j]) {
        dfs_sz (j, i);
        sz[i] += sz[j];
    }
    vis[i] = tt;
return sz[i];}
int dfs_cen (int i, int par, int tot) {
    for (int j : e[i]) if (j != par and !block[j] and sz[j] * 2 > tot) return dfs_cen(j, i, tot);
    return i;
}
void solve (int st) {
    vector <int> color_used = {st};
    queue<int> q;
    tt2++;
    ins[st] = tt2;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59