oj.uz

Submission #538152

# Submission time Handle Problem Language Result Execution time Memory
538152 2022-03-16T06:27:35 Z Haruto810198 Capital City (JOI20_capital_city) C++17
100 / 100
 1640 ms 181876 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(cidx == 1) cerr<<"add_edge "<<from<<" -> ["<<ml<<", "<<mr<<"] "<<endl;
	// ml, mr, from : dfn of nodes
	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();
		}
	}
	/*	
	cerr<<"sccid : ";
	FOR(v, 1, nodes, 1){
		cerr<<sccid[v]<<' ';
	}
	cerr<<endl;
	*/
	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));
		/*	
		cerr<<"scc_sz["<<v<<"] = "<<scc_sz[v]<<", ";
		cerr<<"edge_scc["<<v<<"] : ";
		for(int i : edge_scc[v]){
			cerr<<i<<' ';
		}
		cerr<<endl;
		*/
	}
	
	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);
	/*	
	cerr<<"dfn : ";
	FOR(i, 1, n, 1){
		cerr<<dfn[i]<<' ';
	}
	cerr<<endl;
	*/
	// 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 22 ms 37972 KB Output is correct
2 Correct 25 ms 37916 KB Output is correct
3 Correct 22 ms 37880 KB Output is correct
4 Correct 21 ms 37972 KB Output is correct
5 Correct 20 ms 37916 KB Output is correct
6 Correct 23 ms 37972 KB Output is correct
7 Correct 20 ms 37972 KB Output is correct
8 Correct 20 ms 37972 KB Output is correct
9 Correct 21 ms 37944 KB Output is correct
10 Correct 20 ms 37972 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37972 KB Output is correct
2 Correct 25 ms 37916 KB Output is correct
3 Correct 22 ms 37880 KB Output is correct
4 Correct 21 ms 37972 KB Output is correct
5 Correct 20 ms 37916 KB Output is correct
6 Correct 23 ms 37972 KB Output is correct
7 Correct 20 ms 37972 KB Output is correct
8 Correct 20 ms 37972 KB Output is correct
9 Correct 21 ms 37944 KB Output is correct
10 Correct 20 ms 37972 KB Output is correct
11 Correct 27 ms 39072 KB Output is correct
12 Correct 28 ms 39124 KB Output is correct
13 Correct 31 ms 39128 KB Output is correct
14 Correct 25 ms 39116 KB Output is correct
15 Correct 24 ms 39008 KB Output is correct
16 Correct 25 ms 39132 KB Output is correct
17 Correct 24 ms 38996 KB Output is correct
18 Correct 24 ms 38992 KB Output is correct
19 Correct 23 ms 38996 KB Output is correct
20 Correct 24 ms 39044 KB Output is correct
21 Correct 24 ms 39104 KB Output is correct
22 Correct 27 ms 39124 KB Output is correct
23 Correct 28 ms 39140 KB Output is correct
24 Correct 23 ms 38788 KB Output is correct
25 Correct 25 ms 38928 KB Output is correct
26 Correct 24 ms 38944 KB Output is correct
27 Correct 25 ms 38996 KB Output is correct
28 Correct 25 ms 38932 KB Output is correct
29 Correct 26 ms 38944 KB Output is correct
30 Correct 27 ms 39004 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 176568 KB Output is correct
2 Correct 382 ms 177180 KB Output is correct
3 Correct 734 ms 177912 KB Output is correct
4 Correct 424 ms 177048 KB Output is correct
5 Correct 700 ms 175740 KB Output is correct
6 Correct 382 ms 176604 KB Output is correct
7 Correct 715 ms 174480 KB Output is correct
8 Correct 418 ms 167580 KB Output is correct
9 Correct 878 ms 157020 KB Output is correct
10 Correct 812 ms 153888 KB Output is correct
11 Correct 805 ms 158056 KB Output is correct
12 Correct 796 ms 158252 KB Output is correct
13 Correct 789 ms 152856 KB Output is correct
14 Correct 772 ms 159024 KB Output is correct
15 Correct 826 ms 158452 KB Output is correct
16 Correct 795 ms 154140 KB Output is correct
17 Correct 828 ms 154636 KB Output is correct
18 Correct 800 ms 156460 KB Output is correct
19 Correct 849 ms 158652 KB Output is correct
20 Correct 775 ms 158732 KB Output is correct
21 Correct 22 ms 37972 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37972 KB Output is correct
2 Correct 25 ms 37916 KB Output is correct
3 Correct 22 ms 37880 KB Output is correct
4 Correct 21 ms 37972 KB Output is correct
5 Correct 20 ms 37916 KB Output is correct
6 Correct 23 ms 37972 KB Output is correct
7 Correct 20 ms 37972 KB Output is correct
8 Correct 20 ms 37972 KB Output is correct
9 Correct 21 ms 37944 KB Output is correct
10 Correct 20 ms 37972 KB Output is correct
11 Correct 27 ms 39072 KB Output is correct
12 Correct 28 ms 39124 KB Output is correct
13 Correct 31 ms 39128 KB Output is correct
14 Correct 25 ms 39116 KB Output is correct
15 Correct 24 ms 39008 KB Output is correct
16 Correct 25 ms 39132 KB Output is correct
17 Correct 24 ms 38996 KB Output is correct
18 Correct 24 ms 38992 KB Output is correct
19 Correct 23 ms 38996 KB Output is correct
20 Correct 24 ms 39044 KB Output is correct
21 Correct 24 ms 39104 KB Output is correct
22 Correct 27 ms 39124 KB Output is correct
23 Correct 28 ms 39140 KB Output is correct
24 Correct 23 ms 38788 KB Output is correct
25 Correct 25 ms 38928 KB Output is correct
26 Correct 24 ms 38944 KB Output is correct
27 Correct 25 ms 38996 KB Output is correct
28 Correct 25 ms 38932 KB Output is correct
29 Correct 26 ms 38944 KB Output is correct
30 Correct 27 ms 39004 KB Output is correct
31 Correct 777 ms 176568 KB Output is correct
32 Correct 382 ms 177180 KB Output is correct
33 Correct 734 ms 177912 KB Output is correct
34 Correct 424 ms 177048 KB Output is correct
35 Correct 700 ms 175740 KB Output is correct
36 Correct 382 ms 176604 KB Output is correct
37 Correct 715 ms 174480 KB Output is correct
38 Correct 418 ms 167580 KB Output is correct
39 Correct 878 ms 157020 KB Output is correct
40 Correct 812 ms 153888 KB Output is correct
41 Correct 805 ms 158056 KB Output is correct
42 Correct 796 ms 158252 KB Output is correct
43 Correct 789 ms 152856 KB Output is correct
44 Correct 772 ms 159024 KB Output is correct
45 Correct 826 ms 158452 KB Output is correct
46 Correct 795 ms 154140 KB Output is correct
47 Correct 828 ms 154636 KB Output is correct
48 Correct 800 ms 156460 KB Output is correct
49 Correct 849 ms 158652 KB Output is correct
50 Correct 775 ms 158732 KB Output is correct
51 Correct 22 ms 37972 KB Output is correct
52 Correct 1593 ms 177972 KB Output is correct
53 Correct 1624 ms 180624 KB Output is correct
54 Correct 1598 ms 181876 KB Output is correct
55 Correct 1582 ms 180044 KB Output is correct
56 Correct 1594 ms 180680 KB Output is correct
57 Correct 1640 ms 179196 KB Output is correct
58 Correct 814 ms 154892 KB Output is correct
59 Correct 833 ms 154552 KB Output is correct
60 Correct 1050 ms 170656 KB Output is correct
61 Correct 1093 ms 178176 KB Output is correct
62 Correct 416 ms 177648 KB Output is correct
63 Correct 395 ms 177792 KB Output is correct
64 Correct 391 ms 170172 KB Output is correct
65 Correct 402 ms 177328 KB Output is correct
66 Correct 824 ms 170864 KB Output is correct
67 Correct 830 ms 170680 KB Output is correct
68 Correct 818 ms 170808 KB Output is correct
69 Correct 792 ms 170780 KB Output is correct
70 Correct 838 ms 170732 KB Output is correct
71 Correct 856 ms 170800 KB Output is correct
72 Correct 791 ms 170860 KB Output is correct
73 Correct 899 ms 172340 KB Output is correct
74 Correct 809 ms 170692 KB Output is correct
75 Correct 789 ms 170828 KB Output is correct
76 Correct 685 ms 129972 KB Output is correct
77 Correct 635 ms 128084 KB Output is correct
78 Correct 837 ms 156628 KB Output is correct
79 Correct 819 ms 152040 KB Output is correct
80 Correct 802 ms 159520 KB Output is correct
81 Correct 812 ms 158880 KB Output is correct
82 Correct 817 ms 158576 KB Output is correct
83 Correct 787 ms 153012 KB Output is correct
84 Correct 923 ms 158656 KB Output is correct
85 Correct 853 ms 158884 KB Output is correct
86 Correct 785 ms 151772 KB Output is correct
87 Correct 823 ms 155040 KB Output is correct
88 Correct 854 ms 162088 KB Output is correct
89 Correct 833 ms 159388 KB Output is correct
90 Correct 851 ms 159628 KB Output is correct
91 Correct 838 ms 161552 KB Output is correct
92 Correct 915 ms 160356 KB Output is correct
93 Correct 856 ms 158532 KB Output is correct
94 Correct 824 ms 157224 KB Output is correct
95 Correct 837 ms 160728 KB Output is correct
96 Correct 890 ms 158276 KB Output is correct
97 Correct 852 ms 171488 KB Output is correct