oj.uz

Submission #414116

# Submission time Handle Problem Language Result Execution time Memory
414116 2021-05-30T05:21:50 Z nathanlee726 Mergers (JOI19_mergers) C++14
24 / 100
 211 ms 89856 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);}
vector<int> g[500010],la[500010],gr[500010];
int di[500010],st[500010],pa[500010],fr[500010],si[500010],fa[500010],ct[500010],ind=0,l[500010],r[500010],ST[1000010][20],id[1000010],ct2[500010];
int find(int x){ 
	if(fr[x]!=x)fr[x]=find(fr[x]);
	return fr[x];
} 
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return;
	if(si[x]>si[y])swap(x,y);
	fr[x]=y;
	si[y]+=si[x];
}
void dfs1(int p,int f,int d){
	id[ind]=p;
	di[p]=d;
	l[p]=ind++;
	for(int u:g[p]){
		if(u==f)continue;
		dfs1(u,p,d+1);
	}
	id[ind]=p;
	r[p]=ind++;
}
void dfs(int p,int f,int d){
	fa[p]=f;
	pa[p]=d-la[st[p]].back();
	la[st[p]].pb(d);
	for(int u:g[p]){
		if(u==f)continue;
		dfs(u,p,d+1);
	}
	la[st[p]].pop_back(); 
}
void dfs2(int p,int f){
	for(int u:g[p]){
		if(u==f)continue;
		if(find(p)!=find(u))ct2[find(p)]++,ct2[find(u)]++;
		dfs2(u,p);
	}
} 
int LCA(int x,int y){
	int li=min(l[x],l[y]),ri=max(r[x],r[y]);
	bug(li,ri);
	int len=ri-li+1;
	int lg=__lg(len);
	return (di[ST[li][lg]]<di[ST[ri-(1<<lg)+1][lg]]?ST[li][lg]:ST[ri-(1<<lg)+1][lg]);
}
signed main(){
	IOS();
	int n,k;
	cin>>n>>k;
	if(n==1){
		cout<<"0"<<endl;
		return 0;
	}
	F(n-1){
		int x,y;
		cin>>x>>y;
		--x,--y;
		g[x].pb(y);
		g[y].pb(x);
	}
	F(n)cin>>st[i];
	F(n){
		gr[st[i]].pb(i);
	}
	dfs1(0,-1,1);
	F(2*n)ST[i][0]=id[i];
	Fi(j,19)for(int i=0;i+(1<<(j+1))-1<2*n;i++){
		ST[i][j+1]=(di[ST[i][j]]<di[ST[i+(1<<j)][j]]?ST[i][j]:ST[i+(1<<j)][j]);
	}
	F(k){
		int np=gr[i+1][0];
		Fi(j,sz(gr[i+1])-1){
			np=LCA(np,gr[i+1][j+1]);
		}	
		la[i+1].pb(di[np]);
	}
	dfs(0,-1,1);
	F(n)fr[i]=i,si[i]=1,ct[i]=sz(g[i]);
	F(k){
		if(sz(gr[i+1])>=2){
			Fi(j,sz(gr[i+1])-1){
				merge(gr[i+1][j],gr[i+1][j+1]);
			}
		}
	}
	queue<pii> q;
	F(n){
		if(sz(g[i])==1&&i!=0){
			q.push({i,pa[i]});
		}
	}
	while(!q.empty()){
		pii tmp=q.front();q.pop();
		if(tmp.Y>0)merge(tmp.X,fa[tmp.X]);
		tmp.X=fa[tmp.X];
		tmp.Y=max(pa[tmp.X],tmp.Y-1);
		if(tmp.X!=-1){
			ct[tmp.X]--;
			pa[tmp.X]=max(tmp.Y,pa[tmp.X]);
			if(ct[tmp.X]==1)q.push(tmp); 
		} 
	}
	dfs2(0,-1);
	int ans=0;
	F(n){
		bug(pa[i]);
		if(ct2[i]==1)ans++;
	}
	ans=ceiling(ans,2);
	cout<<ans<<endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 20 ms 35648 KB Output is correct
3 Correct 21 ms 35636 KB Output is correct
4 Correct 21 ms 35540 KB Output is correct
5 Correct 21 ms 35548 KB Output is correct
6 Correct 21 ms 35644 KB Output is correct
7 Correct 20 ms 35548 KB Output is correct
8 Correct 20 ms 35684 KB Output is correct
9 Correct 21 ms 35596 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 20 ms 35688 KB Output is correct
12 Correct 20 ms 35580 KB Output is correct
13 Correct 21 ms 35544 KB Output is correct
14 Correct 23 ms 35844 KB Output is correct
15 Correct 20 ms 35660 KB Output is correct
16 Correct 20 ms 35524 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 20 ms 35636 KB Output is correct
19 Correct 25 ms 35532 KB Output is correct
20 Correct 21 ms 35592 KB Output is correct
21 Correct 21 ms 35660 KB Output is correct
22 Correct 21 ms 35788 KB Output is correct
23 Correct 20 ms 35532 KB Output is correct
24 Correct 20 ms 35604 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 20 ms 35648 KB Output is correct
3 Correct 21 ms 35636 KB Output is correct
4 Correct 21 ms 35540 KB Output is correct
5 Correct 21 ms 35548 KB Output is correct
6 Correct 21 ms 35644 KB Output is correct
7 Correct 20 ms 35548 KB Output is correct
8 Correct 20 ms 35684 KB Output is correct
9 Correct 21 ms 35596 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 20 ms 35688 KB Output is correct
12 Correct 20 ms 35580 KB Output is correct
13 Correct 21 ms 35544 KB Output is correct
14 Correct 23 ms 35844 KB Output is correct
15 Correct 20 ms 35660 KB Output is correct
16 Correct 20 ms 35524 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 20 ms 35636 KB Output is correct
19 Correct 25 ms 35532 KB Output is correct
20 Correct 21 ms 35592 KB Output is correct
21 Correct 21 ms 35660 KB Output is correct
22 Correct 21 ms 35788 KB Output is correct
23 Correct 20 ms 35532 KB Output is correct
24 Correct 20 ms 35604 KB Output is correct
25 Correct 20 ms 35688 KB Output is correct
26 Incorrect 23 ms 37068 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 20 ms 35648 KB Output is correct
3 Correct 21 ms 35636 KB Output is correct
4 Correct 21 ms 35540 KB Output is correct
5 Correct 21 ms 35548 KB Output is correct
6 Correct 21 ms 35644 KB Output is correct
7 Correct 20 ms 35548 KB Output is correct
8 Correct 20 ms 35684 KB Output is correct
9 Correct 21 ms 35596 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 20 ms 35688 KB Output is correct
12 Correct 20 ms 35580 KB Output is correct
13 Correct 21 ms 35544 KB Output is correct
14 Correct 23 ms 35844 KB Output is correct
15 Correct 20 ms 35660 KB Output is correct
16 Correct 20 ms 35524 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 20 ms 35636 KB Output is correct
19 Correct 25 ms 35532 KB Output is correct
20 Correct 21 ms 35592 KB Output is correct
21 Correct 21 ms 35660 KB Output is correct
22 Correct 21 ms 35788 KB Output is correct
23 Correct 20 ms 35532 KB Output is correct
24 Correct 20 ms 35604 KB Output is correct
25 Correct 20 ms 35608 KB Output is correct
26 Correct 157 ms 83432 KB Output is correct
27 Correct 188 ms 82448 KB Output is correct
28 Correct 24 ms 37048 KB Output is correct
29 Correct 22 ms 35596 KB Output is correct
30 Correct 23 ms 35660 KB Output is correct
31 Correct 173 ms 82368 KB Output is correct
32 Correct 24 ms 37072 KB Output is correct
33 Correct 206 ms 89260 KB Output is correct
34 Correct 195 ms 82488 KB Output is correct
35 Correct 24 ms 37004 KB Output is correct
36 Correct 180 ms 82552 KB Output is correct
37 Correct 23 ms 36932 KB Output is correct
38 Correct 24 ms 36968 KB Output is correct
39 Correct 179 ms 83312 KB Output is correct
40 Correct 26 ms 37196 KB Output is correct
41 Correct 164 ms 82260 KB Output is correct
42 Correct 211 ms 84096 KB Output is correct
43 Correct 20 ms 35688 KB Output is correct
44 Correct 186 ms 89328 KB Output is correct
45 Correct 205 ms 87136 KB Output is correct
46 Correct 22 ms 37068 KB Output is correct
47 Correct 23 ms 36964 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 83412 KB Output is correct
2 Correct 185 ms 89856 KB Output is correct
3 Incorrect 25 ms 37096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 35532 KB Output is correct
2 Correct 20 ms 35648 KB Output is correct
3 Correct 21 ms 35636 KB Output is correct
4 Correct 21 ms 35540 KB Output is correct
5 Correct 21 ms 35548 KB Output is correct
6 Correct 21 ms 35644 KB Output is correct
7 Correct 20 ms 35548 KB Output is correct
8 Correct 20 ms 35684 KB Output is correct
9 Correct 21 ms 35596 KB Output is correct
10 Correct 22 ms 35532 KB Output is correct
11 Correct 20 ms 35688 KB Output is correct
12 Correct 20 ms 35580 KB Output is correct
13 Correct 21 ms 35544 KB Output is correct
14 Correct 23 ms 35844 KB Output is correct
15 Correct 20 ms 35660 KB Output is correct
16 Correct 20 ms 35524 KB Output is correct
17 Correct 23 ms 35532 KB Output is correct
18 Correct 20 ms 35636 KB Output is correct
19 Correct 25 ms 35532 KB Output is correct
20 Correct 21 ms 35592 KB Output is correct
21 Correct 21 ms 35660 KB Output is correct
22 Correct 21 ms 35788 KB Output is correct
23 Correct 20 ms 35532 KB Output is correct
24 Correct 20 ms 35604 KB Output is correct
25 Correct 20 ms 35688 KB Output is correct
26 Incorrect 23 ms 37068 KB Output isn't correct
27 Halted 0 ms 0 KB -