oj.uz

Submission #790228

# Submission time Handle Problem Language Result Execution time Memory
790228 2023-07-22T12:49:49 Z kshitij_sodani Unique Cities (JOI19_ho_t5) C++14
4 / 100
 2000 ms 53392 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;
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){
			ne++;
			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){
		int ne=mm[0].a+1;
		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;

	//lev-1 to lev-ma[no]
	
	for(auto j:kk){
		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);
	int n,m;
	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;
	}

	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++){
		cout<<ans[i]<<endl;
	}


	

	


	return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 7 ms 9868 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 15 ms 10080 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 15 ms 10088 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 7 ms 10068 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 9 ms 10000 KB Output is correct
16 Correct 5 ms 9940 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 13 ms 10068 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 8 ms 10128 KB Output is correct
21 Correct 18 ms 9996 KB Output is correct
22 Correct 6 ms 9940 KB Output is correct
23 Correct 7 ms 9996 KB Output is correct
24 Correct 7 ms 9872 KB Output is correct
25 Correct 8 ms 9864 KB Output is correct
26 Correct 6 ms 9940 KB Output is correct
27 Correct 8 ms 10068 KB Output is correct
28 Correct 7 ms 9996 KB Output is correct
29 Correct 16 ms 10000 KB Output is correct
30 Correct 7 ms 9868 KB Output is correct
31 Correct 9 ms 10068 KB Output is correct
32 Correct 18 ms 10124 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 20028 KB Output is correct
2 Correct 155 ms 29504 KB Output is correct
3 Correct 1798 ms 14784 KB Output is correct
4 Correct 194 ms 30380 KB Output is correct
5 Correct 306 ms 44320 KB Output is correct
6 Execution timed out 2044 ms 45220 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 30320 KB Output is correct
2 Correct 603 ms 53392 KB Output is correct
3 Execution timed out 2070 ms 15872 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 7 ms 9868 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 15 ms 10080 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 15 ms 10088 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 7 ms 10068 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 9 ms 10000 KB Output is correct
16 Correct 5 ms 9940 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 13 ms 10068 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 8 ms 10128 KB Output is correct
21 Correct 18 ms 9996 KB Output is correct
22 Correct 6 ms 9940 KB Output is correct
23 Correct 7 ms 9996 KB Output is correct
24 Correct 7 ms 9872 KB Output is correct
25 Correct 8 ms 9864 KB Output is correct
26 Correct 6 ms 9940 KB Output is correct
27 Correct 8 ms 10068 KB Output is correct
28 Correct 7 ms 9996 KB Output is correct
29 Correct 16 ms 10000 KB Output is correct
30 Correct 7 ms 9868 KB Output is correct
31 Correct 9 ms 10068 KB Output is correct
32 Correct 18 ms 10124 KB Output is correct
33 Correct 105 ms 20028 KB Output is correct
34 Correct 155 ms 29504 KB Output is correct
35 Correct 1798 ms 14784 KB Output is correct
36 Correct 194 ms 30380 KB Output is correct
37 Correct 306 ms 44320 KB Output is correct
38 Execution timed out 2044 ms 45220 KB Time limit exceeded
39 Halted 0 ms 0 KB -