Submission #542963

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
542963	2022-03-28 14:42:06	chonka	Capital City (JOI20_capital_city)	C++98	1 / 100	714 ms	42804 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 ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define MAXN 200007
int n , k ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
vector < int > col[ MAXN ] ;
int tot ;
int used[ MAXN ] , subtree[ MAXN ] , prv[ MAXN ] , mrk[ MAXN ] ;
bool added[ MAXN ] ;
vector < int > clist ;
int ans = MAXN ; 
void dfs ( int vertex , int lst , int ori ) {
    mrk[ vertex ] = ori ;
    ++ tot ;
    subtree[ vertex ] = 1 ;
    for ( auto x : v[ vertex ] ) {
        if ( x == lst || used[ x ] == 1 ) { continue ; }
        prv[ x ] = vertex ;
        dfs ( x , vertex , ori ) ;
        subtree[ vertex ] += subtree[ x ] ;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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