oj.uz

Submission #538153

# Submission time Handle Problem Language Result Execution time Memory
538153 2022-03-16T06:31:06 Z Haruto810198 Capital City (JOI20_capital_city) C++17
100 / 100
 1571 ms 180096 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int, int>
 
#define F first
#define S second
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const double eps = 1e-12;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n, k;
vi edge_t[MAX];
int city[MAX];
vi occ[MAX];
int res;

// HLD
int par[MAX], sz[MAX], dep[MAX], heavy[MAX], dfn[MAX], fr[MAX];
int ts;

// segment tree optimization
#define V st[cidx]

struct Node{
	int lc, rc;
	int sl, sr;
};
int nodes = 1;
Node st[2*MAX];
int leaf[MAX]; // leaf[i] = id. of node [i, i] in st
int w[2*MAX];

// SCC
vi edge_g[2*MAX];
vi edge_g_rev[2*MAX];
vi dfstk;
vi cur_scc;
bool vis[2*MAX];
int scccnt;
int sccid[2*MAX];
vi edge_scc[2*MAX];
int scc_sz[2*MAX];

// ===============================================================

// HLD
void find_heavy(int v, int pv){
	par[v] = pv;
	sz[v] = 1;
	if(v == pv) dep[v] = 0;
	else dep[v] = dep[pv] + 1;
	
	int Max = 0;
	heavy[v] = -1;
	for(int i : edge_t[v]){
		if(i == pv) continue;
		find_heavy(i, v);
		sz[v] += sz[i];
		if(Max < sz[i]){
			Max = sz[i];
			heavy[v] = i;
		}
	}
}

void HLD(int v, int pv, int frv){
	dfn[v] = ++ts;
	fr[v] = frv;
	
	if(heavy[v] != -1) HLD(heavy[v], v, frv);

	for(int i : edge_t[v]){
		if(i == pv or i == heavy[v]) continue;
		HLD(i, v, i);
	}
}

vector<pii> Segs(int u, int v){
	vector<pii> ret;
	while(fr[u] != fr[v]){
		if(dep[fr[u]] > dep[fr[v]]) swap(u, v);
		ret.eb(dfn[fr[v]], dfn[v]);
		v = par[fr[v]];
	}

	if(dep[u] > dep[v]) swap(u, v);
	ret.eb(dfn[u], dfn[v]);

	return ret;
}

// segment tree
void build(int cidx, int cl, int cr){
	V.sl = cl;
	V.sr = cr;
	if(cl < cr){
		int mid = (cl + cr) / 2;
		
		V.lc = ++nodes;
		edge_g[cidx].pb(V.lc);
		build(nodes, cl, mid);

		V.rc = ++nodes;
		edge_g[cidx].pb(V.rc);
		build(nodes, mid+1, cr);
	}
	else{
		leaf[cl] = cidx;
	}
}

void add_edge(int cidx, int ml, int mr, int from){
	if(mr < V.sl or V.sr < ml) return;
	if(ml <= V.sl and V.sr <= mr){
		edge_g[leaf[from]].pb(cidx);
		return;
	}

	add_edge(V.lc, ml, mr, from);
	add_edge(V.rc, ml, mr, from);
}

// SCC
void dfs1(int v){
	vis[v] = 1;
	for(int i : edge_g[v]){
		if(vis[i] == 0) dfs1(i);
	}
	dfstk.pb(v);
}

void dfs2(int v){
	vis[v] = 1;
	for(int i : edge_g_rev[v]){
		if(vis[i] == 0) dfs2(i);
	}
	cur_scc.pb(v);
}

void find_sccs(){

	FOR(v, 1, nodes, 1){
		if(vis[v] == 0) dfs1(v);
	}
	
	FOR(v, 1, nodes, 1){
		for(int i : edge_g[v]){
			edge_g_rev[i].pb(v);
		}
		vis[v] = 0;
	}
	
	while(!dfstk.empty()){
		int v = dfstk.back();
		dfstk.pop_back();

		if(vis[v] == 0){
			dfs2(v);
			scccnt++;
			for(int i : cur_scc){
				sccid[i] = scccnt;
				scc_sz[scccnt] += w[i];
			}
			cur_scc.clear();
		}
	}
	FOR(v, 1, nodes, 1){
		for(int i : edge_g[v]){
			if(sccid[v] != sccid[i]) edge_scc[sccid[v]].pb(sccid[i]);
		}
	}
	
	FOR(v, 1, scccnt, 1){
		auto it = unique(edge_scc[v].begin(), edge_scc[v].end());
		edge_scc[v].resize(distance(edge_scc[v].begin(), it));
	}
	
	res = INF;
	FOR(v, 1, scccnt, 1){
		if(edge_scc[v].empty()) res = min(res, scc_sz[v]);
	}
}

signed main(){
	
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n>>k;
	FOR(i, 1, n-1, 1){
		int u, v;
		cin>>u>>v;
		edge_t[u].pb(v);
		edge_t[v].pb(u);
	}

	FOR(i, 1, n, 1){
		cin>>city[i];
		occ[city[i]].pb(i);
	}

	// HLD
	find_heavy(1, 1);
	HLD(1, 1, 1);

	// segment tree
	build(1, 1, n);
	FOR(i, 1, k, 1){
		FOR(j, 0, szof(occ[i])-2, 1){
			int u = occ[i][j], v = occ[i][j+1]; // u, v = id. of nodes
			vector<pii> segs = Segs(u, v);
			for(pii p : segs){
				add_edge(1, p.F, p.S, dfn[u]);
			}
			add_edge(1, dfn[u], dfn[u], dfn[v]);
		}
	}
	
	// w
	FOR(i, 1, k, 1){
		int v = occ[i].front();
		w[leaf[dfn[v]]] = 1;
	}

	// SCC
	find_sccs();
	
	cout<<res - 1<<'\n';
	
	return 0;
	
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37972 KB Output is correct
2 Correct 22 ms 37996 KB Output is correct
3 Correct 20 ms 37972 KB Output is correct
4 Correct 23 ms 37968 KB Output is correct
5 Correct 20 ms 37972 KB Output is correct
6 Correct 20 ms 38004 KB Output is correct
7 Correct 20 ms 37992 KB Output is correct
8 Correct 20 ms 37956 KB Output is correct
9 Correct 20 ms 37972 KB Output is correct
10 Correct 20 ms 37940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37972 KB Output is correct
2 Correct 22 ms 37996 KB Output is correct
3 Correct 20 ms 37972 KB Output is correct
4 Correct 23 ms 37968 KB Output is correct
5 Correct 20 ms 37972 KB Output is correct
6 Correct 20 ms 38004 KB Output is correct
7 Correct 20 ms 37992 KB Output is correct
8 Correct 20 ms 37956 KB Output is correct
9 Correct 20 ms 37972 KB Output is correct
10 Correct 20 ms 37940 KB Output is correct
11 Correct 26 ms 39108 KB Output is correct
12 Correct 26 ms 39156 KB Output is correct
13 Correct 27 ms 39056 KB Output is correct
14 Correct 25 ms 39048 KB Output is correct
15 Correct 24 ms 38996 KB Output is correct
16 Correct 27 ms 38988 KB Output is correct
17 Correct 24 ms 39112 KB Output is correct
18 Correct 24 ms 38980 KB Output is correct
19 Correct 26 ms 39060 KB Output is correct
20 Correct 24 ms 39096 KB Output is correct
21 Correct 22 ms 39076 KB Output is correct
22 Correct 21 ms 39124 KB Output is correct
23 Correct 24 ms 39120 KB Output is correct
24 Correct 27 ms 38792 KB Output is correct
25 Correct 23 ms 38996 KB Output is correct
26 Correct 24 ms 39048 KB Output is correct
27 Correct 25 ms 39092 KB Output is correct
28 Correct 24 ms 39020 KB Output is correct
29 Correct 23 ms 39000 KB Output is correct
30 Correct 24 ms 39020 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 176812 KB Output is correct
2 Correct 396 ms 176040 KB Output is correct
3 Correct 700 ms 176980 KB Output is correct
4 Correct 384 ms 176120 KB Output is correct
5 Correct 688 ms 174688 KB Output is correct
6 Correct 385 ms 175488 KB Output is correct
7 Correct 698 ms 173324 KB Output is correct
8 Correct 366 ms 166584 KB Output is correct
9 Correct 761 ms 155844 KB Output is correct
10 Correct 731 ms 152836 KB Output is correct
11 Correct 736 ms 157056 KB Output is correct
12 Correct 744 ms 157348 KB Output is correct
13 Correct 737 ms 151916 KB Output is correct
14 Correct 769 ms 158020 KB Output is correct
15 Correct 734 ms 157360 KB Output is correct
16 Correct 730 ms 153188 KB Output is correct
17 Correct 733 ms 153588 KB Output is correct
18 Correct 751 ms 155304 KB Output is correct
19 Correct 757 ms 157612 KB Output is correct
20 Correct 727 ms 157752 KB Output is correct
21 Correct 20 ms 37972 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37972 KB Output is correct
2 Correct 22 ms 37996 KB Output is correct
3 Correct 20 ms 37972 KB Output is correct
4 Correct 23 ms 37968 KB Output is correct
5 Correct 20 ms 37972 KB Output is correct
6 Correct 20 ms 38004 KB Output is correct
7 Correct 20 ms 37992 KB Output is correct
8 Correct 20 ms 37956 KB Output is correct
9 Correct 20 ms 37972 KB Output is correct
10 Correct 20 ms 37940 KB Output is correct
11 Correct 26 ms 39108 KB Output is correct
12 Correct 26 ms 39156 KB Output is correct
13 Correct 27 ms 39056 KB Output is correct
14 Correct 25 ms 39048 KB Output is correct
15 Correct 24 ms 38996 KB Output is correct
16 Correct 27 ms 38988 KB Output is correct
17 Correct 24 ms 39112 KB Output is correct
18 Correct 24 ms 38980 KB Output is correct
19 Correct 26 ms 39060 KB Output is correct
20 Correct 24 ms 39096 KB Output is correct
21 Correct 22 ms 39076 KB Output is correct
22 Correct 21 ms 39124 KB Output is correct
23 Correct 24 ms 39120 KB Output is correct
24 Correct 27 ms 38792 KB Output is correct
25 Correct 23 ms 38996 KB Output is correct
26 Correct 24 ms 39048 KB Output is correct
27 Correct 25 ms 39092 KB Output is correct
28 Correct 24 ms 39020 KB Output is correct
29 Correct 23 ms 39000 KB Output is correct
30 Correct 24 ms 39020 KB Output is correct
31 Correct 689 ms 176812 KB Output is correct
32 Correct 396 ms 176040 KB Output is correct
33 Correct 700 ms 176980 KB Output is correct
34 Correct 384 ms 176120 KB Output is correct
35 Correct 688 ms 174688 KB Output is correct
36 Correct 385 ms 175488 KB Output is correct
37 Correct 698 ms 173324 KB Output is correct
38 Correct 366 ms 166584 KB Output is correct
39 Correct 761 ms 155844 KB Output is correct
40 Correct 731 ms 152836 KB Output is correct
41 Correct 736 ms 157056 KB Output is correct
42 Correct 744 ms 157348 KB Output is correct
43 Correct 737 ms 151916 KB Output is correct
44 Correct 769 ms 158020 KB Output is correct
45 Correct 734 ms 157360 KB Output is correct
46 Correct 730 ms 153188 KB Output is correct
47 Correct 733 ms 153588 KB Output is correct
48 Correct 751 ms 155304 KB Output is correct
49 Correct 757 ms 157612 KB Output is correct
50 Correct 727 ms 157752 KB Output is correct
51 Correct 20 ms 37972 KB Output is correct
52 Correct 1449 ms 176112 KB Output is correct
53 Correct 1453 ms 178712 KB Output is correct
54 Correct 1485 ms 180096 KB Output is correct
55 Correct 1480 ms 177832 KB Output is correct
56 Correct 1428 ms 178564 KB Output is correct
57 Correct 1571 ms 177172 KB Output is correct
58 Correct 811 ms 152748 KB Output is correct
59 Correct 742 ms 152492 KB Output is correct
60 Correct 963 ms 168780 KB Output is correct
61 Correct 1004 ms 176056 KB Output is correct
62 Correct 394 ms 175540 KB Output is correct
63 Correct 388 ms 175560 KB Output is correct
64 Correct 367 ms 167920 KB Output is correct
65 Correct 380 ms 175196 KB Output is correct
66 Correct 739 ms 168684 KB Output is correct
67 Correct 780 ms 168628 KB Output is correct
68 Correct 797 ms 168568 KB Output is correct
69 Correct 745 ms 168528 KB Output is correct
70 Correct 750 ms 168700 KB Output is correct
71 Correct 750 ms 168584 KB Output is correct
72 Correct 753 ms 168480 KB Output is correct
73 Correct 798 ms 170148 KB Output is correct
74 Correct 787 ms 168372 KB Output is correct
75 Correct 732 ms 168676 KB Output is correct
76 Correct 635 ms 127628 KB Output is correct
77 Correct 581 ms 125696 KB Output is correct
78 Correct 763 ms 154160 KB Output is correct
79 Correct 769 ms 149648 KB Output is correct
80 Correct 715 ms 157224 KB Output is correct
81 Correct 743 ms 156552 KB Output is correct
82 Correct 740 ms 156236 KB Output is correct
83 Correct 726 ms 150752 KB Output is correct
84 Correct 740 ms 156344 KB Output is correct
85 Correct 732 ms 156652 KB Output is correct
86 Correct 717 ms 149608 KB Output is correct
87 Correct 757 ms 152716 KB Output is correct
88 Correct 811 ms 159664 KB Output is correct
89 Correct 783 ms 157112 KB Output is correct
90 Correct 781 ms 157252 KB Output is correct
91 Correct 794 ms 159272 KB Output is correct
92 Correct 778 ms 157900 KB Output is correct
93 Correct 756 ms 156188 KB Output is correct
94 Correct 769 ms 154952 KB Output is correct
95 Correct 792 ms 158404 KB Output is correct
96 Correct 788 ms 155876 KB Output is correct
97 Correct 816 ms 169152 KB Output is correct