oj.uz

Submission #927439

# Submission time Handle Problem Language Result Execution time Memory
927439 2024-02-14T20:58:03 Z AdamGS Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 48764 KB 
#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], wys[LIM], jaki[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) {
	++ile[x];
	if(ile[x]==1) ++aktile;
}
void usun(int x) {
	--ile[x];
	if(ile[x]==0) --aktile;
}
void schodz() {
	while(trma[1]>0) {
		int p=zejdzma(1, 0, N-1);
		usun(T[ojcowie[p]]);
		upd(1, 0, N-1, p, p, -INF);
	}
	while(trmi[1]==-INF) {
		int p=zejdzmi(1, 0, N-1);
		dodaj(T[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);
	dodaj(T[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);
	}
	schodz();
  usun(T[x]);
	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, m) ile[i]=0;
	aktile=0;
	DFS2(y, y);
	DFS3(y, y, 1);
	rep(i, n) cout << wynik[i] << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 5 ms 9564 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9564 KB Output is correct
9 Correct 5 ms 9800 KB Output is correct
10 Correct 5 ms 9560 KB Output is correct
11 Correct 6 ms 9560 KB Output is correct
12 Correct 4 ms 9564 KB Output is correct
13 Correct 18 ms 9820 KB Output is correct
14 Correct 11 ms 9820 KB Output is correct
15 Correct 10 ms 9820 KB Output is correct
16 Correct 4 ms 9560 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 6 ms 9564 KB Output is correct
20 Correct 7 ms 9820 KB Output is correct
21 Correct 6 ms 9820 KB Output is correct
22 Correct 6 ms 9600 KB Output is correct
23 Correct 6 ms 9600 KB Output is correct
24 Correct 5 ms 9564 KB Output is correct
25 Correct 5 ms 9564 KB Output is correct
26 Correct 4 ms 9596 KB Output is correct
27 Correct 34 ms 10076 KB Output is correct
28 Correct 14 ms 9820 KB Output is correct
29 Correct 10 ms 9684 KB Output is correct
30 Correct 4 ms 9792 KB Output is correct
31 Correct 6 ms 9820 KB Output is correct
32 Correct 6 ms 9820 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20164 KB Output is correct
2 Correct 464 ms 31444 KB Output is correct
3 Correct 71 ms 15176 KB Output is correct
4 Correct 588 ms 27440 KB Output is correct
5 Correct 967 ms 47008 KB Output is correct
6 Correct 843 ms 37244 KB Output is correct
7 Correct 572 ms 27608 KB Output is correct
8 Correct 1128 ms 29536 KB Output is correct
9 Correct 829 ms 28832 KB Output is correct
10 Correct 961 ms 28764 KB Output is correct
11 Correct 353 ms 28060 KB Output is correct
12 Execution timed out 2053 ms 37104 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 25680 KB Output is correct
2 Correct 891 ms 47248 KB Output is correct
3 Correct 84 ms 15668 KB Output is correct
4 Correct 604 ms 28304 KB Output is correct
5 Correct 1006 ms 48764 KB Output is correct
6 Correct 984 ms 38452 KB Output is correct
7 Correct 554 ms 28324 KB Output is correct
8 Execution timed out 2060 ms 28376 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 5 ms 9564 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9820 KB Output is correct
6 Correct 6 ms 9820 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 5 ms 9564 KB Output is correct
9 Correct 5 ms 9800 KB Output is correct
10 Correct 5 ms 9560 KB Output is correct
11 Correct 6 ms 9560 KB Output is correct
12 Correct 4 ms 9564 KB Output is correct
13 Correct 18 ms 9820 KB Output is correct
14 Correct 11 ms 9820 KB Output is correct
15 Correct 10 ms 9820 KB Output is correct
16 Correct 4 ms 9560 KB Output is correct
17 Correct 5 ms 9820 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 6 ms 9564 KB Output is correct
20 Correct 7 ms 9820 KB Output is correct
21 Correct 6 ms 9820 KB Output is correct
22 Correct 6 ms 9600 KB Output is correct
23 Correct 6 ms 9600 KB Output is correct
24 Correct 5 ms 9564 KB Output is correct
25 Correct 5 ms 9564 KB Output is correct
26 Correct 4 ms 9596 KB Output is correct
27 Correct 34 ms 10076 KB Output is correct
28 Correct 14 ms 9820 KB Output is correct
29 Correct 10 ms 9684 KB Output is correct
30 Correct 4 ms 9792 KB Output is correct
31 Correct 6 ms 9820 KB Output is correct
32 Correct 6 ms 9820 KB Output is correct
33 Correct 333 ms 20164 KB Output is correct
34 Correct 464 ms 31444 KB Output is correct
35 Correct 71 ms 15176 KB Output is correct
36 Correct 588 ms 27440 KB Output is correct
37 Correct 967 ms 47008 KB Output is correct
38 Correct 843 ms 37244 KB Output is correct
39 Correct 572 ms 27608 KB Output is correct
40 Correct 1128 ms 29536 KB Output is correct
41 Correct 829 ms 28832 KB Output is correct
42 Correct 961 ms 28764 KB Output is correct
43 Correct 353 ms 28060 KB Output is correct
44 Execution timed out 2053 ms 37104 KB Time limit exceeded
45 Halted 0 ms 0 KB -