oj.uz

Submission #790238

# Submission time Handle Problem Language Result Execution time Memory
790238 2023-07-22T13:01:31 Z kshitij_sodani Unique Cities (JOI19_ho_t5) C++14
64 / 100
 502 ms 61640 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'

int it[200001];
vector<int> adj[200001];
vector<int> adj2[200001];
int vis[200001];
int val[200001];
int ans[200001];
pair<int,int> ma={-1,-1};
int par2[200001];
void dfs(int no,int par=-1,int levv=0){
	ma=max(ma,{levv,no});
	par2[no]=par;
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no,levv+1);
		}
	}
}
void dfs2(int no,int par=-1,int levv=0){
	ma=max(ma,{levv,no});
	par2[no]=par;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs2(j,no,levv+1);
		}
	}
}
int pp;
/*void dfs3(int no,int par=-1,int levv=0){
	ma=max(ma,{levv,no});
	par2[no]=par;
	ans[no]=pp;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs3(j,no,levv+1);
		}
	}
}*/

map<int,int> ee;
int co=0;
void add(int i){
	ee[it[i]]++;
	if(ee[it[i]]==1){
		co++;
	}
}
void remove(int i){
	ee[it[i]]--;
	if(ee[it[i]]==0){
		co--;
	}
}
//set<pair<int,int>> zz;
int ma2[200001];
void dfs4(int no,int par=-1,int lev=0){
	ma2[no]=0;
	for(auto j:adj2[no]){
		if(j!=par){
			dfs4(j,no,lev+1);
			ma2[no]=max(ma2[no],ma2[j]+1);
		}
	}
}

set<pair<int,int>> zz;
pair<int,int> tree[4*200001];
int lazy[4*200001];
void build(int no,int l,int r){
	tree[no]={0,r-l+1};
	lazy[no]=0;
	if(l==r){
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
	}

}
void push(int no,int l,int r){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];

	}
	lazy[no]=0;

}
pair<int,int> merge(pair<int,int> x,pair<int,int> y){
	if(x.a<y.a){
		return x;
	}
	if(y.a<x.a){
		return y;
	}
	return {x.a,x.b+y.b};
}
void update(int no,int l,int r,int aa,int bb,int x){
	if(lazy[no]!=0){
		push(no,l,r);
	}
	if(bb<l or r<aa or aa>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]=x;
		push(no,l,r);
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,x);
		update(no*2+2,mid+1,r,aa,bb,x);
		tree[no]=merge(tree[no*2+1],tree[no*2+2]);
	}
}
pair<int,int> query(int no,int l,int r,int aa,int bb){
	push(no,l,r);

	if(r<aa or l>bb or aa>bb){
		return {1e8,0};
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	int mid=(l+r)/2;
	pair<int,int> x=query(no*2+1,l,mid,aa,bb);
	pair<int,int> y=query(no*2+2,mid+1,r,aa,bb);
	tree[no]=merge(tree[no*2+1],tree[no*2+2]);
	return merge(x,y);

}
int n,m;
void dfs5(int no,int par=-1,int lev=0){
	vector<pair<int,int>> mm;
	//cout<<no<<";";

	for(auto j:adj2[no]){
		if(j!=par){
			mm.pb({ma2[j],j});
		}
	}
	sort(mm.begin(),mm.end());
	reverse(mm.begin(),mm.end());
	vector<pair<int,int>> kk;
	//add(no);
	//zz.insert({lev,no});
	int ind3=-1;
	for(auto j:mm){
		ind3++;
		int ne=-1;
		if(ind3==0){
			if(mm.size()>=2){
				ne=mm[1].a;
			}
		}
		else if(ind3==1){
			ne=mm[0].a;;
		}
		if(ne>=0 and lev>0){
			ne++;
			update(0,0,n-1,max(lev-ne,0),max(lev-1,0),1);
			kk.pb({max(lev-ne,0),max(lev-1,0)});
			/*auto jj=zz.lower_bound({lev-ne,-1});
			vector<pair<int,int>> ll;
			while(jj!=zz.end()){
				if((*jj).a>=lev){
					break;
				}
				remove((*jj).b);
				ll.pb(*jj);
				jj++;
			}
			for(auto ii:ll){
				kk.pb(ii);
				zz.erase(ii);
			}*/
		}
		dfs5(j.b,no,lev+1);
	}
	if(mm.size()==1 and lev>0){
		int ne=mm[0].a+1;
		update(0,0,n-1,max(lev-ne,0),max(lev-1,0),1);
		kk.pb({max(lev-ne,0),max(lev-1,0)});
		/*auto jj=zz.lower_bound({lev-ne,-1});
		vector<pair<int,int>> ll;
		while(jj!=zz.end()){
			if((*jj).a>=lev){
				break;
			}
			remove((*jj).b);
			ll.pb(*jj);
			jj++;
		}
		for(auto ii:ll){
			kk.pb(ii);
			zz.erase(ii);
		}*/
	}
	//zz.erase({lev,no});
	//remove(no);

	ans[no]=co;
	pair<int,int> x=query(0,0,n-1,0,lev-1);
	if(x.a==0){
		ans[no]+=x.b;
	}
	//lev-1 to lev-ma[no]
	
	for(auto j:kk){
		update(0,0,n-1,j.a,j.b,-1);
	//	zz.insert(j);
		//add(j.b);
	}
}
int ha=0;

void solve(vector<int> ss){
	set<pair<int,int>> tt;
	ee.clear();
	co=0;

	//map of present colours
	int ind=ss.size();
	for(int i=0;i<ss.size();i++){
		tt.insert({i,ss[i]});
	}
	for(int i=ss.size()-1;i>=0;i--){

		auto j=tt.lower_bound({i+1,-1});
		vector<pair<int,int>> kk;
		while(j!=tt.end()){
			if((*j).a>i+val[ss[i]]){
				break;
			}
			if((*j).a>=ind){
				remove((*j).b);
			}
			kk.pb(*j);
			j++;
			/*if(ss[0]==1){
				cout<<(*j).b<<"?"<<endl;

			}*/
		}
		for(auto j:kk){
			tt.erase(j);
		}
		if(i<(int)(ss.size())-i-1){
			int ind2=2*i+1;
			while(ind>ind2){
				ind--;
				if(tt.find({ind,ss[ind]})!=tt.end()){
					add(ss[ind]);
				}
			}
			ans[ss[i]]=co;
			//continue;
		/*	if(ss[i]==0){
				for(auto jj:ee){
					cout<<jj.a<<",,"<<jj.b<<endl;
				}
			}*/
			dfs4(ss[i]);
		/*	if(ss[i]==0){
				cout<<ma2[ss[i]]<<"?"<<endl;
			}*/
			dfs5(ss[i]);
		//	cout<<endl;
			//ans[ss[i]]=co;
		}
		if(i==(int)ss.size()-i-1 and ha==0){
			ha=1;
			dfs4(ss[i]);
			dfs5(ss[i]);

		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>m;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	dfs(0);
	int x=ma.b;
	ma={-1,-1};
	dfs(x);
	dfs2(x);

	vector<int> ss;
	int cur=ma.b;
	while(true){
		ss.pb(cur);
		cur=par2[cur];
		if(cur==-1){
			break;
		}
	}
	for(auto j:ss){
		vis[j]=1;
	}
	for(int i=0;i<n;i++){
		for(auto j:adj[i]){
			if(vis[i]+vis[j]<2){
				adj2[i].pb(j);
			}
		}
	}

	for(auto j:ss){
		ma={-1,-1};
		dfs2(j);
		val[j]=ma.a;
	//cout<<j<<":"<<ma.a<<endl;
	}
	build(0,0,n-1);

	solve(ss);
	reverse(ss.begin(),ss.end());
	solve(ss);
/*	for(auto j:ss){
		pp=ans[j];
		dfs3(j);
	}*/
	for(int i=0;i<n;i++){
		if(m==1){
			cout<<min(ans[i],1)<<endl;
			continue;
		}
		cout<<ans[i]<<endl;
	}


	

	


	return 0;
}

Compilation message

joi2019_ho_t5.cpp: In function 'void solve(std::vector<int>)':
joi2019_ho_t5.cpp:233:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |  for(int i=0;i<ss.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 6 ms 9940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 23012 KB Output is correct
2 Correct 133 ms 31052 KB Output is correct
3 Correct 36 ms 14780 KB Output is correct
4 Correct 305 ms 33612 KB Output is correct
5 Correct 294 ms 47484 KB Output is correct
6 Correct 311 ms 44996 KB Output is correct
7 Correct 263 ms 35756 KB Output is correct
8 Correct 276 ms 38468 KB Output is correct
9 Correct 311 ms 37984 KB Output is correct
10 Correct 284 ms 38504 KB Output is correct
11 Correct 175 ms 37668 KB Output is correct
12 Correct 356 ms 46596 KB Output is correct
13 Correct 263 ms 44904 KB Output is correct
14 Correct 275 ms 47448 KB Output is correct
15 Correct 176 ms 37604 KB Output is correct
16 Correct 231 ms 46712 KB Output is correct
17 Correct 266 ms 48176 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 29896 KB Output is correct
2 Correct 461 ms 56024 KB Output is correct
3 Correct 42 ms 15288 KB Output is correct
4 Correct 281 ms 37312 KB Output is correct
5 Correct 502 ms 61640 KB Output is correct
6 Correct 339 ms 48788 KB Output is correct
7 Correct 331 ms 36560 KB Output is correct
8 Correct 293 ms 41360 KB Output is correct
9 Correct 342 ms 40228 KB Output is correct
10 Correct 288 ms 39692 KB Output is correct
11 Correct 242 ms 37164 KB Output is correct
12 Correct 432 ms 54424 KB Output is correct
13 Correct 344 ms 45444 KB Output is correct
14 Correct 306 ms 48288 KB Output is correct
15 Correct 162 ms 38712 KB Output is correct
16 Correct 389 ms 53960 KB Output is correct
17 Correct 295 ms 49128 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 6 ms 9940 KB Output isn't correct
3 Halted 0 ms 0 KB -