Submission #137194

#	Time	Username	Problem	Language	Result	Execution time	Memory
137194		hamzqq9	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	530 ms	38264 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 200005
#define MOD 998244353
using namespace std;

int n,m;
int mxd[N][2],der[N];
int ans[N],c[N],deep[N];
int s[N];
int sz;
int tot_op;
int cntd;
int cnt[N];
vector<int> v[N];

struct diameter_finder {

	int l,r;
	int mx;

	void dfs(int node,int ata,int len) {

		if(len>mx) {

			mx=len;
			l=node;

		}

		for(int i:v[node]) {

			if(i==ata) continue ;

			dfs(i,node,len+1);

		}

	}
 
	void find() {

		mx=0;

		dfs(1,0,0);

		r=l;

		mx=0;

		dfs(r,0,0);

	}

} dia;

void add(int node) {

	s[++sz]=node;

//	++tot_op;

	cntd+=(cnt[c[node]]==0);

	cnt[c[node]]++;

}

void del(int cur) {

	while(sz && cur<=der[s[sz]]) {

		//++tot_op;

		cnt[c[s[sz]]]--;

		cntd-=(cnt[c[s[sz]]]==0);

		--sz;

	}

}

void upd(int node,int nd) {

	if(mxd[node][1]<nd) mxd[node][1]=nd;

	if(mxd[node][1]>mxd[node][0]) swap(mxd[node][1],mxd[node][0]);

}

void dfs(int node,int ata) {

	del(2*der[node]-mxd[node][1]);

	add(node);

	for(int i:v[node]) {

		if(i!=deep[node]) continue ;

		dfs(i,node);

	}

	del(2*der[node]-mxd[node][0]);
	
	umax(ans[node],cntd);

	for(int i:v[node]) {

		if(i==ata || i==deep[node]) continue ;

		if(!sz || s[sz]!=node) add(node);

		dfs(i,node);

	}

	del(der[node]);

}

void dfs1(int node,int ata) {

	der[node]=der[ata]+1;

	mxd[node][0]=mxd[node][1]=der[node];

	deep[node]=node;

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs1(i,node);

		upd(node,mxd[i][0]);

		if(mxd[node][0]==mxd[i][0]) {

			deep[node]=i;

		}

	}

}

int main() {

	scanf("%d %d",&n,&m);

	for(int i=1;i<n;i++) {

		int x,y;

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

	}

	for(int i=1;i<=n;i++) scanf("%d",c+i);

	dia.find();

//	cerr << "root is : " << dia.l << '\n';

	dfs1(dia.l,0);
	dfs(dia.l,0);

//	cerr << "root is : " << dia.r << '\n';

	dfs1(dia.r,0);
	dfs(dia.r,0);

	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);

//	cerr << tot_op << '\n';

}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:177:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",c+i);
                        ~~~~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32