Submission #466966

#	Time	Username	Problem	Language	Result	Execution time	Memory
466966		jamezzz	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	426 ms	41528 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define ppb pop_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 200005

int n,m,rt=1,a,b,c[maxn],num[maxn],ans[maxn],d[maxn],f[maxn],l[maxn][2],cnt;
vi s,AL[maxn];

void dfs1(int u,int p){ //find furthest
	for(int v:AL[u]){
		if(v==p)continue;
		d[v]=d[u]+1;
		if(d[v]>d[rt])rt=v;
		dfs1(v,u);
	}
}

void dfs2(int u,int p){ //find heavy child
	l[u][0]=l[u][1]=0;
	for(int v:AL[u]){
		if(v==p)continue;
		d[v]=d[u]+1;
		dfs2(v,u);
		if(f[v]>f[l[u][1]])l[u][1]=v;
		if(f[l[u][1]]>f[l[u][0]])swap(l[u][0],l[u][1]);
	}
	f[u]=f[l[u][0]]+1;
}

void add(int i){
	if(num[c[i]]==0)++cnt;
	++num[c[i]];
}

void rem(int i){
	if(num[c[i]]==1)--cnt;
	--num[c[i]];
}

void dfs3(int u,int p){
	if(p)add(p),s.pb(p);
	if(l[u][0]){
		while(!s.empty()&&d[s.back()]>=d[u]-f[l[u][1]]){
			rem(s.back());s.ppb();
		}
		dfs3(l[u][0],u);
	}
	while(!s.empty()&&d[s.back()]>=d[u]-f[l[u][0]]){
		rem(s.back());s.ppb();
	}
	for(int v:AL[u]){
		if(v!=p&&v!=l[u][0])dfs3(v,u);
	}
	mxto(ans[u],cnt);
	if(!s.empty()&&s.back()==p){
		rem(s.back());s.ppb();
	}
	
}

void idk(int x){
	d[x]=0;
	dfs1(x,0);
	d[rt]=0;
	dfs2(rt,0);
	cnt=0;s.clear();
	for(int i=1;i<=n;++i)num[i]=0;
	dfs3(rt,0);
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=1;i<n;++i){
		sf("%d%d",&a,&b);
		AL[a].pb(b);AL[b].pb(a);
	}
	for(int i=1;i<=n;++i){
		sf("%d",&c[i]);
	}
	idk(1);idk(rt);
	for(int i=1;i<=n;++i){
		pf("%d\n",ans[i]);
	}
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:100:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  sf("%d%d",&n,&m);
      |    ^
joi2019_ho_t5.cpp:102:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   sf("%d%d",&a,&b);
      |     ^
joi2019_ho_t5.cpp:106:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   sf("%d",&c[i]);
      |     ^

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