oj.uz

답안 #520816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520816 2022-01-31T04:58:17 Z nathanlee726 수도 (JOI20_capital_city) C++14
11 / 100
 1355 ms 524292 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
 
int n,k,dep[200010],ord[200010],pa[200010][20],inde=0,ind,id=0,pt[200010][20],co[200010],cnt[5000010],ou[5000010];
vector<int> g[500010],rg[5000010],cl[200010];
 
void dfs(int p,int f,int d){
	dep[p]=d;
	ord[p]=inde++;
	pa[p][0]=f;
	for(int j=0;j<18;j++){if(pa[p][j]!=-1)pa[p][j+1]=pa[pa[p][j]][j];else pa[p][j+1]=-1;}
	if(p!=0){
		pt[p][0]=ind++;
		assert(ind<=5000000);
		rg[pt[p][0]].pb(p);
		rg[pt[p][0]].pb(pa[p][0]);
		for(int j=1;(1ll<<j)<=dep[p];j++){
			pt[p][j]=ind++;
			rg[pt[p][j]].pb(p);
			rg[pt[p][j]].pb(pt[p][j-1]);
			assert(pa[p][j-1]!=-1);
			rg[pt[p][j]].pb(pt[pa[p][j-1]][j-1]);
		}
	}
	for(int u:g[p]){
		if(u==f)continue;
		dfs(u,p,d+1);
	}
}
 
bool cmp(int x,int y){
	return ord[x]<ord[y];
}
 
void ad_ed(int p,int l){
	int tp=p;
	assert(l>=0);
	for(int i=18;i>=0;i--){
		if((1ll<<i)&l)rg[p].pb(pt[tp][i]),tp=pa[tp][i];
	}
}
 
void lca_ed(int x,int y){
	if(x==y)return;
	int rx=x,ry=y;
	int xd=dep[x],yd=dep[y];
	if(xd>yd)swap(x,y),swap(xd,yd),swap(rx,ry);
	int len=yd-xd;
	for(int i=19;i>=0;i--){
		if((1ll<<i)&len)y=pa[y][i];
	}
	int r;
	if(x==y)r=dep[x];
	else{
	for(int i=19;i>=0;i--){
		if(pa[x][i]==-1)continue;
		if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
	}
	r=pa[x][0];
	r=dep[r];
	}
	int xl=xd-r,yl=yd-r;
	bug(rx,xl,ry,yl);
	if(xl>0)ad_ed(rx,xl);
	if(yl>0)ad_ed(ry,yl);
}
 
vector<int> sta;
int dfn[5000010],low[5000010],ind1=0,gr[5000010];
bool inst[5000010]={0};
 
void tarjan(int p){
	dfn[p]=low[p]=++ind1;
	inst[p]=1;
	sta.pb(p);
	for(int u:rg[p]){
		if(dfn[u]==0){
			tarjan(u);
			low[p]=min(low[p],low[u]);
		}
		else if(inst[u]){
			low[p]=min(low[p],dfn[u]);
		}
	}
	if(low[p]==dfn[p]){
		id++;
		while(sta.back()!=p){
			inst[sta.back()]=0;
			gr[sta.back()]=id;
			bug(id,sta.back());
			sta.pop_back();
		}
		//assert(sta.back()==p);
		inst[p]=0;
		gr[p]=id;
		bug(id,p);
		sta.pop_back();
	}
}
 
signed main(){
	IOS();
	cin>>n>>k;
	F(n-1){
		int x,y;
		cin>>x>>y;
		//x=i+1,y=i+2;
		--x,--y;
		g[x].pb(y);
		g[y].pb(x);
	}
	ind=n;
	dfs(0,-1,0);
	F(n){
		int x;
		cin>>x;
		//x=0;
		--x;
		cl[x].pb(i);
		co[i]=x;
	}
	F(k){
		if(sz(cl[i])>=2){
			sort(all(cl[i]),cmp);
			cl[i].pb(cl[i][0]);
			Fi(j,sz(cl[i])-1){
				bug(cl[i][j],cl[i][j+1]);
				rg[cl[i][j]].pb(cl[i][j+1]);
				lca_ed(cl[i][j],cl[i][j+1]);
			}
		}
	}
	memres(dfn);
	memres(low);
	memres(cnt);
	F(ind){
		if(dfn[i]==0)tarjan(i);
	}
	//memres(ou);
	//return 0;
	F(ind){
		if(sz(rg[i]))for(int j:rg[i]){
			if(gr[i]!=gr[j]){
				ou[gr[i]]++;
			}
		}
	}
	F(k){
		if(sz(cl[i]))cnt[gr[cl[i][0]]]++;
	}
	/*F(ind){
		bug(i);
		for(int j:rg[i])cout<<j<<" ";
		cout<<endl;
	}*/
	bug(id);
	int ans=n;
	for(int i=1;i<=id;i++)bug(cnt[i],ou[i]);
	for(int i=1;i<=id;i++)if(cnt[i]!=0&&ou[i]==0)ans=min(ans,cnt[i]);
	cout<<ans-1<<endl;
	return 0;
}
/*
10 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
5 4 1 3 2 3 2 1 4 5
 
20 10
19 6
6 3
3 18
18 20
20 11
11 7
7 17
17 14
14 9
9 13
13 5
5 12
12 4
4 10
10 2
2 16
16 15
15 8
8 1
8
3
2
6
7
5
7
5
1
1
4
9
4
6
2
10
9
10
8
3
 
20 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
8 5 2 10 3 1 6 9 7 4 1 6 9 7 4 3 10 2 5 8
*/

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 192832 KB Output is correct
2 Correct 90 ms 192924 KB Output is correct
3 Correct 82 ms 192840 KB Output is correct
4 Correct 80 ms 192836 KB Output is correct
5 Correct 81 ms 192932 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 100 ms 192840 KB Output is correct
8 Correct 80 ms 192820 KB Output is correct
9 Correct 81 ms 192896 KB Output is correct
10 Correct 84 ms 192868 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 192832 KB Output is correct
2 Correct 90 ms 192924 KB Output is correct
3 Correct 82 ms 192840 KB Output is correct
4 Correct 80 ms 192836 KB Output is correct
5 Correct 81 ms 192932 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 100 ms 192840 KB Output is correct
8 Correct 80 ms 192820 KB Output is correct
9 Correct 81 ms 192896 KB Output is correct
10 Correct 84 ms 192868 KB Output is correct
11 Correct 85 ms 193792 KB Output is correct
12 Correct 85 ms 193896 KB Output is correct
13 Correct 86 ms 193884 KB Output is correct
14 Correct 84 ms 193848 KB Output is correct
15 Correct 85 ms 194160 KB Output is correct
16 Correct 84 ms 194064 KB Output is correct
17 Correct 97 ms 194112 KB Output is correct
18 Correct 89 ms 194088 KB Output is correct
19 Correct 84 ms 194172 KB Output is correct
20 Correct 90 ms 194196 KB Output is correct
21 Correct 95 ms 194116 KB Output is correct
22 Correct 90 ms 195164 KB Output is correct
23 Correct 86 ms 194372 KB Output is correct
24 Correct 87 ms 194152 KB Output is correct
25 Correct 88 ms 194444 KB Output is correct
26 Correct 87 ms 194400 KB Output is correct
27 Correct 86 ms 194324 KB Output is correct
28 Correct 86 ms 194300 KB Output is correct
29 Correct 94 ms 194332 KB Output is correct
30 Correct 87 ms 194244 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1355 ms 514132 KB Output is correct
2 Runtime error 842 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 192832 KB Output is correct
2 Correct 90 ms 192924 KB Output is correct
3 Correct 82 ms 192840 KB Output is correct
4 Correct 80 ms 192836 KB Output is correct
5 Correct 81 ms 192932 KB Output is correct
6 Correct 81 ms 192848 KB Output is correct
7 Correct 100 ms 192840 KB Output is correct
8 Correct 80 ms 192820 KB Output is correct
9 Correct 81 ms 192896 KB Output is correct
10 Correct 84 ms 192868 KB Output is correct
11 Correct 85 ms 193792 KB Output is correct
12 Correct 85 ms 193896 KB Output is correct
13 Correct 86 ms 193884 KB Output is correct
14 Correct 84 ms 193848 KB Output is correct
15 Correct 85 ms 194160 KB Output is correct
16 Correct 84 ms 194064 KB Output is correct
17 Correct 97 ms 194112 KB Output is correct
18 Correct 89 ms 194088 KB Output is correct
19 Correct 84 ms 194172 KB Output is correct
20 Correct 90 ms 194196 KB Output is correct
21 Correct 95 ms 194116 KB Output is correct
22 Correct 90 ms 195164 KB Output is correct
23 Correct 86 ms 194372 KB Output is correct
24 Correct 87 ms 194152 KB Output is correct
25 Correct 88 ms 194444 KB Output is correct
26 Correct 87 ms 194400 KB Output is correct
27 Correct 86 ms 194324 KB Output is correct
28 Correct 86 ms 194300 KB Output is correct
29 Correct 94 ms 194332 KB Output is correct
30 Correct 87 ms 194244 KB Output is correct
31 Correct 1355 ms 514132 KB Output is correct
32 Runtime error 842 ms 524292 KB Execution killed with signal 9
33 Halted 0 ms 0 KB -