oj.uz

Submission #372689

# Submission time Handle Problem Language Result Execution time Memory
372689 2021-03-01T09:56:17 Z alishahali1382 Unique Cities (JOI19_ho_t5) C++14
64 / 100
 1622 ms 46204 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=200010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
int C[MAXN], par[MAXN], h[MAXN], ans[MAXN];
pii D[MAXN];
pii seg[MAXN<<2];
int lazy[MAXN<<2];
vector<int> G[MAXN];

inline void add_lazy(int id, int val){
	seg[id].first+=val;
	lazy[id]+=val;
}
inline void shift(int id){
	if (!lazy[id]) return ;
	add_lazy(id<<1, lazy[id]);
	add_lazy(id<<1 | 1, lazy[id]);
	lazy[id]=0;
}
inline pii Merge(pii x, pii y){
	return (x.first==y.first?pii(x.first, x.second+y.second):min(x, y));
}
pii Build(int id, int tl, int tr){
	lazy[id]=0;
	if (tr-tl==1) return seg[id]={0, 1};
	int mid=(tl+tr)>>1;
	return seg[id]=Merge(Build(id<<1, tl, mid), Build(id<<1 | 1, mid, tr));
}
void Add(int id, int tl, int tr, int l, int r, int val){
	if (r<=tl || tr<=l) return ;
//	if (id==1) cerr<<"Add "<<l<<" "<<r<<"  "<<val<<"\n";
	if (l<=tl && tr<=r){
		add_lazy(id, val);
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, val);
	Add(id<<1 | 1, mid, tr, l, r, val);
	seg[id]=Merge(seg[id<<1], seg[id<<1 | 1]);
}
pii Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return seg[0];
	if (l<=tl && tr<=r) return seg[id];
	shift(id);
	int mid=(tl+tr)>>1;
	return Merge(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

void dfs1(int node, int p){
	par[node]=p;
	h[node]=h[p]+1;
	D[node]={0, node};
	for (int v:G[node]) if (v!=p){
		dfs1(v, node);
		D[node]=max(D[node], {D[v].first+1, D[v].second});
	}
}
void dfs2(int node){
	pii p=Get(1, 1, n+1, 1, h[node]-D[node].first);
	if (!p.first) ans[node]=max(ans[node], p.second);/*
	if (node==1){
		debugp(p)
		cerr<<"NODE=1\n\n\n";
	}*/
	for (int v:G[node]) if (v!=par[node]) Add(1, 1, n+1, h[node]-D[v].first-1, h[node], +1);
	for (int v:G[node]) if (v!=par[node]){
		Add(1, 1, n+1, h[node]-D[v].first-1, h[node], -1);
		dfs2(v);
		Add(1, 1, n+1, h[node]-D[v].first-1, h[node], +1);
	}
	for (int v:G[node]) if (v!=par[node]) Add(1, 1, n+1, h[node]-D[v].first-1, h[node], -1);
}
void Solve(int root){
//	debug(root)
	dfs1(root, 0);
	Build(1, 1, n+1);
//	for (int i=1; i<=n; i++) debugp(D[i])
//	debug(h[1])
	dfs2(root);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m;
	for (int i=1; i<n; i++){
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	for (int i=1; i<=n; i++) cin>>C[i];
	
	dfs1(1, 0);
	int root=D[1].second;
	Solve(root);
	dfs1(root, 0); // pashm
	root=D[root].second;
	Solve(root);
	
//	Solve(5);
	for (int i=1; i<=n; i++) cout<<min(ans[i], m)<<"\n";
	
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 10 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 14796 KB Output is correct
2 Correct 824 ms 27116 KB Output is correct
3 Correct 155 ms 9324 KB Output is correct
4 Correct 1217 ms 25664 KB Output is correct
5 Correct 1587 ms 44524 KB Output is correct
6 Correct 1568 ms 35068 KB Output is correct
7 Correct 1166 ms 25852 KB Output is correct
8 Correct 1270 ms 27628 KB Output is correct
9 Correct 1255 ms 26988 KB Output is correct
10 Correct 1299 ms 27040 KB Output is correct
11 Correct 953 ms 26500 KB Output is correct
12 Correct 1474 ms 37356 KB Output is correct
13 Correct 1366 ms 35188 KB Output is correct
14 Correct 1504 ms 34520 KB Output is correct
15 Correct 918 ms 26208 KB Output is correct
16 Correct 1424 ms 38376 KB Output is correct
17 Correct 1526 ms 35376 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 20332 KB Output is correct
2 Correct 1526 ms 44604 KB Output is correct
3 Correct 184 ms 9708 KB Output is correct
4 Correct 1201 ms 26476 KB Output is correct
5 Correct 1622 ms 46204 KB Output is correct
6 Correct 1579 ms 36332 KB Output is correct
7 Correct 1161 ms 26556 KB Output is correct
8 Correct 1330 ms 30700 KB Output is correct
9 Correct 1272 ms 29164 KB Output is correct
10 Correct 1285 ms 28140 KB Output is correct
11 Correct 1095 ms 26984 KB Output is correct
12 Correct 1540 ms 42276 KB Output is correct
13 Correct 1389 ms 34904 KB Output is correct
14 Correct 1530 ms 35048 KB Output is correct
15 Correct 984 ms 27240 KB Output is correct
16 Correct 1483 ms 39776 KB Output is correct
17 Correct 1603 ms 36220 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Incorrect 10 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -