Submission #928580

#	Time	Username	Problem	Language	Result	Execution time	Memory
928580		AdamGS	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	919 ms	50472 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, INF=1e9+7;
vector<int>V[LIM];
int T[LIM], ile[LIM], wynik[LIM], odl[2][LIM], odw[LIM], wys[LIM], jaki[LIM], czy[LIM], aktile;
int trma[4*LIM], trmi[4*LIM], lazy[4*LIM], N=1;
vector<int>ojcowie;
void spl(int v) {
	trma[2*v]+=lazy[v];
	trma[2*v+1]+=lazy[v];
	trmi[2*v]+=lazy[v];
	trmi[2*v+1]+=lazy[v];
	lazy[2*v]+=lazy[v];
	lazy[2*v+1]+=lazy[v];
	lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
	if(r<a || b<l) return;
	if(a<=l && r<=b) {
		trma[v]+=x;
		trmi[v]+=x;
		lazy[v]+=x;
		return;
	}
	if(lazy[v]) spl(v);
	int mid=(l+r)/2;
	upd(2*v, l, mid, a, b, x);
	upd(2*v+1, mid+1, r, a, b, x);
	trma[v]=max(trma[2*v], trma[2*v+1]);
	trmi[v]=min(trmi[2*v], trmi[2*v+1]);
}
int zejdzmi(int v, int l, int r) {
	if(l==r) return l;
	if(lazy[v]) spl(v);
	int mid=(l+r)/2;
	if(trmi[2*v]<=trmi[2*v+1]) return zejdzmi(2*v, l, mid);
	return zejdzmi(2*v+1, mid+1, r);
}
int zejdzma(int v, int l, int r) {
	if(l==r) return l;
	if(lazy[v]) spl(v);
	int mid=(l+r)/2;
	if(trma[2*v]>=trma[2*v+1]) return zejdzma(2*v, l, mid);
	return zejdzma(2*v+1, mid+1, r);
}
void dodaj(int x) {
  if(odw[x] || !czy[x]) return;
  odw[x]=1;
	++ile[T[x]];
	if(ile[T[x]]==1) ++aktile;
}
void usun(int x) {
  if(!odw[x] || !czy[x]) return;
  odw[x]=0;
	--ile[T[x]];
	if(ile[T[x]]==0) --aktile;
}
void schodz() {
	while(trma[1]>0) {
		int p=zejdzma(1, 0, N-1);
		usun(ojcowie[p]);
		upd(1, 0, N-1, p, p, -INF);
	}
	while(trmi[1]==-INF) {
		int p=zejdzmi(1, 0, N-1);
		dodaj(ojcowie[p]);
		upd(1, 0, N-1, p, p, INF);
	}
}
void DFS(int x, int o, int k) {
	for(auto i : V[x]) if(i!=o) {
		odl[k][i]=odl[k][x]+1;
		DFS(i, x, k);
	}
}
void DFS2(int x, int o) {
	for(auto i : V[x]) if(i!=o) {
		DFS2(i, x);
		wys[x]=max(wys[x], wys[i]+1);
	}
}
void DFS3(int x, int o, int k) {
	ojcowie.pb(x);
	upd(1, 0, N-1, odl[k][x]-wys[x], odl[k][x]-1, 1);
	schodz();
	if(jaki[x]==k) wynik[x]=aktile;
	upd(1, 0, N-1, odl[k][x]-wys[x], odl[k][x]-1, -1);
	czy[x]=1;
  dodaj(x);
	pair<int,int>ma={-1, -1};
	for(auto i : V[x]) if(i!=o) {
		if(wys[i]>=ma.st) {
			ma.nd=ma.st;
			ma.st=wys[i];
		} else ma.nd=max(ma.nd, wys[i]);
	}
	for(auto i : V[x]) if(i!=o) {
		int p=ma.st;
		if(wys[i]==p) p=ma.nd;
		upd(1, 0, N-1, odl[k][x]-p-1, odl[k][x]-1, 1);
		DFS3(i, x, k);
		upd(1, 0, N-1, odl[k][x]-p-1, odl[k][x]-1, -1);
	}
  usun(x);
  czy[x]=0;
	ojcowie.pop_back();
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	while(N<n) N*=2;
	rep(i, n-1) {
		int a, b;
		cin >> a >> b; --a; --b;
		V[a].pb(b);
		V[b].pb(a);
	}
  rep(i, n) {
    cin >> T[i]; --T[i];
  }
	DFS(0, 0, 0);
	pair<int,int>ma={-1, -1};
	rep(i, n) ma=max(ma, {odl[0][i], i});
	int x=ma.nd;
	odl[0][x]=0;
	DFS(x, x, 0);
	ma={-1, -1};
	rep(i, n) ma=max(ma, {odl[0][i], i});
	int y=ma.nd;
	DFS(y, y, 1);
	rep(i, n) if(odl[0][i]<odl[1][i]) jaki[i]=1;
	rep(i, n) wys[i]=0;
	DFS2(x, x);
	DFS3(x, x, 0);
	rep(i, n) wys[i]=0;
	rep(i, 2*N) trma[i]=trmi[i]=lazy[i]=0;
	rep(i, n) odw[i]=czy[i]=0;
  rep(i, m) ile[i]=0;
	aktile=0;
	DFS2(y, y);
	DFS3(y, y, 1);
	rep(i, n) cout << wynik[i] << '\n';
}

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