oj.uz

Submission #97285

# Submission time Handle Problem Language Result Execution time Memory
97285 2019-02-14T18:26:46 Z model_code Unique Cities (JOI19_ho_t5) C++17
100 / 100
 933 ms 47048 KB 
#include <bits/stdc++.h>
#include <type_traits>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

const int Nmax=200010;
vi tr[Nmax];
int ans[Nmax];
int col[Nmax],cnt[Nmax],curAns,stBuf[Nmax],stS;
void AddCol(int c){
	if(cnt[c]==0)
		curAns++;
	cnt[c]++;
}
void DelCol(int c){
	cnt[c]--;
	if(cnt[c]==0)
		curAns--;
}
void Push(int v){
	stBuf[stS++]=v;
	AddCol(col[v]);
}
bool Empty(){
	return stS==0;
}
int Last(){
	return stBuf[stS-1];
}
void Pop(){
	DelCol(col[Last()]);
	stS--;
}

void dfs1(int v,int p,int d,vi&dist){
	dist[v]=d;
	for(auto to:tr[v])
		if(to!=p)
			dfs1(to,v,d+1,dist);
}

int dep[Nmax];
int dfs2(int v,int p){
	int res=0;
	for(auto to:tr[v])
		if(to!=p)
			chmax(res,dfs2(to,v));
	return dep[v]=res+1;
}

void dfs3(int v,int p,const vi&dist){
	vector<pi> ch;
	for(auto to:tr[v])
		if(to!=p)
			ch.EB(dep[to],to);
	if(!ch.empty()){
		swap(ch[0],*max_element(ALL(ch)));
		int len=ch.size()>1?max_element(ch.begin()+1,ch.end())->first:0;
		for(auto c:ch){
			int to=c.second;
			while(!Empty()&&dist[Last()]>=dist[v]-len)
				Pop();
			Push(v);
			dfs3(to,v,dist);
			if(!Empty()&&Last()==v)
				Pop();
			chmax(len,c.first);
		}
		while(!Empty()&&dist[Last()]>=dist[v]-len)
			Pop();
	}
	chmax(ans[v],curAns);
}

void Solve(int root,const vi&dist){
	assert(Empty());
	dfs2(root,-1);
	dfs3(root,-1,dist);
}

signed main(){
	int n=read(),k=read();
	REP(_,n-1){
		int a=read()-1,b=read()-1;
		tr[a].PB(b);
		tr[b].PB(a);
	}
	REP(i,n)
		col[i]=read()-1;
	
	vi dist(n);
	dfs1(0,-1,0,dist);
	int root=max_element(ALL(dist))-dist.begin();
	dfs1(root,-1,0,dist);
	Solve(root,dist);
	
	root=max_element(ALL(dist))-dist.begin();
	dfs1(root,-1,0,dist);
	Solve(root,dist);
	
	REP(i,n)
		print(ans[i]);
}

Compilation message

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:212:15: warning: unused variable 'k' [-Wunused-variable]
  int n=read(),k=read();
               ^
joi2019_ho_t5.cpp: In function 'll read()':
joi2019_ho_t5.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%"  SCNd64,&i);
  ~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'std::__cxx11::string readString()':
joi2019_ho_t5.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",buf);
  ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp: In function 'char* readCharArray()':
joi2019_ho_t5.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",ret);
  ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 10 ms 5376 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 10 ms 5248 KB Output is correct
9 Correct 8 ms 5260 KB Output is correct
10 Correct 7 ms 5212 KB Output is correct
11 Correct 9 ms 5248 KB Output is correct
12 Correct 7 ms 5248 KB Output is correct
13 Correct 10 ms 5376 KB Output is correct
14 Correct 8 ms 5340 KB Output is correct
15 Correct 10 ms 5248 KB Output is correct
16 Correct 8 ms 5248 KB Output is correct
17 Correct 8 ms 5376 KB Output is correct
18 Correct 8 ms 5248 KB Output is correct
19 Correct 11 ms 5120 KB Output is correct
20 Correct 8 ms 5504 KB Output is correct
21 Correct 7 ms 5248 KB Output is correct
22 Correct 10 ms 5164 KB Output is correct
23 Correct 8 ms 5248 KB Output is correct
24 Correct 9 ms 5248 KB Output is correct
25 Correct 8 ms 5248 KB Output is correct
26 Correct 7 ms 5248 KB Output is correct
27 Correct 8 ms 5324 KB Output is correct
28 Correct 7 ms 5376 KB Output is correct
29 Correct 8 ms 5348 KB Output is correct
30 Correct 10 ms 5220 KB Output is correct
31 Correct 7 ms 5376 KB Output is correct
32 Correct 9 ms 5248 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 13096 KB Output is correct
2 Correct 418 ms 27724 KB Output is correct
3 Correct 51 ms 8784 KB Output is correct
4 Correct 617 ms 19236 KB Output is correct
5 Correct 738 ms 44612 KB Output is correct
6 Correct 674 ms 31212 KB Output is correct
7 Correct 490 ms 20472 KB Output is correct
8 Correct 613 ms 22136 KB Output is correct
9 Correct 655 ms 20952 KB Output is correct
10 Correct 690 ms 20884 KB Output is correct
11 Correct 381 ms 26220 KB Output is correct
12 Correct 839 ms 35944 KB Output is correct
13 Correct 689 ms 32848 KB Output is correct
14 Correct 617 ms 30908 KB Output is correct
15 Correct 303 ms 26392 KB Output is correct
16 Correct 694 ms 37044 KB Output is correct
17 Correct 606 ms 31784 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 17304 KB Output is correct
2 Correct 805 ms 45272 KB Output is correct
3 Correct 92 ms 9464 KB Output is correct
4 Correct 726 ms 20632 KB Output is correct
5 Correct 878 ms 47048 KB Output is correct
6 Correct 735 ms 33068 KB Output is correct
7 Correct 639 ms 21152 KB Output is correct
8 Correct 685 ms 26884 KB Output is correct
9 Correct 740 ms 24316 KB Output is correct
10 Correct 674 ms 22580 KB Output is correct
11 Correct 489 ms 23868 KB Output is correct
12 Correct 805 ms 42600 KB Output is correct
13 Correct 667 ms 32888 KB Output is correct
14 Correct 726 ms 31996 KB Output is correct
15 Correct 265 ms 26392 KB Output is correct
16 Correct 588 ms 40188 KB Output is correct
17 Correct 648 ms 33284 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 10 ms 5376 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 10 ms 5248 KB Output is correct
9 Correct 8 ms 5260 KB Output is correct
10 Correct 7 ms 5212 KB Output is correct
11 Correct 9 ms 5248 KB Output is correct
12 Correct 7 ms 5248 KB Output is correct
13 Correct 10 ms 5376 KB Output is correct
14 Correct 8 ms 5340 KB Output is correct
15 Correct 10 ms 5248 KB Output is correct
16 Correct 8 ms 5248 KB Output is correct
17 Correct 8 ms 5376 KB Output is correct
18 Correct 8 ms 5248 KB Output is correct
19 Correct 11 ms 5120 KB Output is correct
20 Correct 8 ms 5504 KB Output is correct
21 Correct 7 ms 5248 KB Output is correct
22 Correct 10 ms 5164 KB Output is correct
23 Correct 8 ms 5248 KB Output is correct
24 Correct 9 ms 5248 KB Output is correct
25 Correct 8 ms 5248 KB Output is correct
26 Correct 7 ms 5248 KB Output is correct
27 Correct 8 ms 5324 KB Output is correct
28 Correct 7 ms 5376 KB Output is correct
29 Correct 8 ms 5348 KB Output is correct
30 Correct 10 ms 5220 KB Output is correct
31 Correct 7 ms 5376 KB Output is correct
32 Correct 9 ms 5248 KB Output is correct
33 Correct 354 ms 13096 KB Output is correct
34 Correct 418 ms 27724 KB Output is correct
35 Correct 51 ms 8784 KB Output is correct
36 Correct 617 ms 19236 KB Output is correct
37 Correct 738 ms 44612 KB Output is correct
38 Correct 674 ms 31212 KB Output is correct
39 Correct 490 ms 20472 KB Output is correct
40 Correct 613 ms 22136 KB Output is correct
41 Correct 655 ms 20952 KB Output is correct
42 Correct 690 ms 20884 KB Output is correct
43 Correct 381 ms 26220 KB Output is correct
44 Correct 839 ms 35944 KB Output is correct
45 Correct 689 ms 32848 KB Output is correct
46 Correct 617 ms 30908 KB Output is correct
47 Correct 303 ms 26392 KB Output is correct
48 Correct 694 ms 37044 KB Output is correct
49 Correct 606 ms 31784 KB Output is correct
50 Correct 519 ms 17304 KB Output is correct
51 Correct 805 ms 45272 KB Output is correct
52 Correct 92 ms 9464 KB Output is correct
53 Correct 726 ms 20632 KB Output is correct
54 Correct 878 ms 47048 KB Output is correct
55 Correct 735 ms 33068 KB Output is correct
56 Correct 639 ms 21152 KB Output is correct
57 Correct 685 ms 26884 KB Output is correct
58 Correct 740 ms 24316 KB Output is correct
59 Correct 674 ms 22580 KB Output is correct
60 Correct 489 ms 23868 KB Output is correct
61 Correct 805 ms 42600 KB Output is correct
62 Correct 667 ms 32888 KB Output is correct
63 Correct 726 ms 31996 KB Output is correct
64 Correct 265 ms 26392 KB Output is correct
65 Correct 588 ms 40188 KB Output is correct
66 Correct 648 ms 33284 KB Output is correct
67 Correct 51 ms 7196 KB Output is correct
68 Correct 256 ms 22808 KB Output is correct
69 Correct 394 ms 21624 KB Output is correct
70 Correct 622 ms 19064 KB Output is correct
71 Correct 727 ms 44576 KB Output is correct
72 Correct 724 ms 31356 KB Output is correct
73 Correct 623 ms 19544 KB Output is correct
74 Correct 720 ms 24660 KB Output is correct
75 Correct 622 ms 21664 KB Output is correct
76 Correct 594 ms 21112 KB Output is correct
77 Correct 477 ms 22628 KB Output is correct
78 Correct 657 ms 38496 KB Output is correct
79 Correct 555 ms 35224 KB Output is correct
80 Correct 679 ms 29820 KB Output is correct
81 Correct 291 ms 26496 KB Output is correct
82 Correct 552 ms 36968 KB Output is correct
83 Correct 615 ms 31756 KB Output is correct
84 Correct 555 ms 19216 KB Output is correct
85 Correct 812 ms 45044 KB Output is correct
86 Correct 882 ms 31304 KB Output is correct
87 Correct 621 ms 19484 KB Output is correct
88 Correct 603 ms 25256 KB Output is correct
89 Correct 618 ms 21884 KB Output is correct
90 Correct 665 ms 21100 KB Output is correct
91 Correct 423 ms 22600 KB Output is correct
92 Correct 763 ms 44396 KB Output is correct
93 Correct 761 ms 29412 KB Output is correct
94 Correct 630 ms 26244 KB Output is correct
95 Correct 286 ms 26520 KB Output is correct
96 Correct 584 ms 36988 KB Output is correct
97 Correct 611 ms 31688 KB Output is correct
98 Correct 586 ms 20792 KB Output is correct
99 Correct 741 ms 45144 KB Output is correct
100 Correct 933 ms 32692 KB Output is correct
101 Correct 740 ms 20536 KB Output is correct
102 Correct 607 ms 24368 KB Output is correct
103 Correct 822 ms 21988 KB Output is correct
104 Correct 747 ms 21356 KB Output is correct
105 Correct 364 ms 22916 KB Output is correct
106 Correct 822 ms 35324 KB Output is correct
107 Correct 775 ms 34944 KB Output is correct
108 Correct 726 ms 28744 KB Output is correct
109 Correct 304 ms 26360 KB Output is correct
110 Correct 583 ms 38572 KB Output is correct
111 Correct 659 ms 32416 KB Output is correct