oj.uz

Submission #154325

# Submission time Handle Problem Language Result Execution time Memory
154325 2019-09-20T16:52:10 Z ryansee Unique Cities (JOI19_ho_t5) C++14
100 / 100
 1024 ms 87188 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}

#define ll /*long long*/ int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <pi, ll> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (200006)
ll n, m; pi roots;
vector<int> v[MAXN];
int A[MAXN], p[MAXN][21]; int st[MAXN], en[MAXN], co;
// pi fdist[MAXN], rdist[MAXN];
ll depth[MAXN];
void init(ll x,ll par) { p[x][0]=par; st[x]=co++;
	// rdist[x] = fdist[x] = pi(depth[x], x); 
	// spi mx=spi(pi(depth[x], x), 1);
	// spi fmx=spi(pi(depth[x], x), 1);
	for(auto i:v[x]) if(i^par) {
		depth[i]=depth[x]+1; init(i, x);
		// rdist[x]=max(rdist[x], rdist[i]);
		// if(rdist[i].f > mx.f.f) mx.f=rdist[i], mx.s=1;
		// else if(rdist[i].f == mx.f.f) ++ mx.s;
		// fmx=max(fmx, fdist[i]);
		// if(fdist[i].f > fmx.f.f) fmx.f=fdist[i], fmx.s=1;
		// else if(fdist[i].f == fmx.f.f) ++ fmx.s;
	}
	// ll rmx=-1;
	// for(auto i:v[x]) if(i^par) {
		// if(fdist[i].f != fmx.f.f) rmx=max(rmx, rdist[i].f);
	// }
	// if(mx.s == 1 && fmx.f.f > rmx && fmx.s==1) fdist[x]=fmx.f; 
	en[x]=co;
}
void t2k() { FOR(j,1,20) FOR(i,1,n) p[i][j]=p[p[i][j-1]][j-1]; }
bool isp(ll a,ll b){return st[a]<=st[b]&&en[a]>=en[b];}
ll lca(ll x,ll y) {
	if(isp(x,y))return x; if(isp(y,x))return y;
	for(ll i=20;i>=0;--i) {
		if(!isp(p[x][i],y))x=p[x][i];
	}
	return p[x][0];
}
// ll ans[MAXN]; 
ll get_dist(ll a,ll b) { return depth[a]+depth[b]-2*depth[lca(a,b)]; }
struct diam_tree {
	int root;
	vector<ll> ans;
	vector <pi> dq;
	ll cur=0;
	ll mp[MAXN];
	ll rdist[MAXN], depth[MAXN];
	ll moves=0;
	void add(ll x, ll d) {
	    assert(++moves <= 5e8);
		// cerr<<x<<" in\n";
		if(!mp[x]) ++ cur;
		++ mp[x];
		dq.eb(x, d);
	}
	void del() { assert(dq.size());
		// cerr<<dq.back().f<<" out\n";
		ll x=dq.back().f;
		-- mp[x];
		if(mp[x] == 0) -- cur;
		dq.pop_back();
	}
	void main() {
		ans.resize(n+1, 0); mmst(mp,0); dq.clear(); mmst(depth,0); mmst(rdist,0);
		assert(root);
		cur=0;
		pre(root, root); dfs(root, root); //cerr<<"r: "<<root<<"\n";
		// FOR(i,1,n) cerr<<i<<": "<<ans[i]<<"\n";
	}
	void dfs(ll x,ll p) {
// 		add(A[x], depth[x]);
		// ans[x]=cur;
		pi one, two;
		one=pi(0, -1);
		two=pi(0, -1);
		for(auto i:v[x]) if(i^p) {
		    two=max(two, pi(rdist[i]-depth[x], i));
		    if(two > one) swap(one, two);
		}
		if(one.s != -1) {
			while(dq.size() && dq.back().s >= depth[x]-two.f) del();
			add(A[x], depth[x]);
			dfs(one.s, x);
		}
		for(auto i:v[x]) if((i^p) && (i^one.s)) {
			while(dq.size() && dq.back().s >= depth[x]-one.f) del();
			add(A[x], depth[x]);
			dfs(i, x);
		}
		while(dq.size() && dq.back().s >= depth[x]-one.f) del();
		ans[x]=cur;
	}
	void pre(ll x,ll p) {
		rdist[x]=depth[x];
		for(auto i:v[x]) if(i^p){
			depth[i]=depth[x]+1;
			pre(i,x);
			rdist[x]=max(rdist[x],rdist[i]);
		}
	}
} r1, r2;
bool can(set<pi,greater<pi>> s) {
	if(s.empty()) return 1;
	ll x = s.begin()->f;
	ll times=1;
	s.erase(s.begin());
	for(auto i:s) {
		if(i.f == x) ++ times;
	}
	return times==1;
}
bool decide(ll x){
	if(get_dist(x, roots.f) >= get_dist(x, roots.s)) return 1;
	else return 0;
}
/*void dfs(ll x,ll par,pi dist,pi rup) {
	spi mx = spi(dist, 1);
	ll rmx=0;
	for(auto i:v[x]) if(i^par) {
		fdist[i].f -= depth[x];
		if(fdist[i].f > mx.f.f) mx.f = fdist[i], mx.s=1;
		else if(fdist[i].f == mx.f.f) ++ mx.s;
		fdist[i].f += depth[x];
		// rmx=max(rmx, rdist[i].f-depth[x]);
	}
	if(mx.f.f != dist.f) rmx=rup.f;
	for(auto i:v[x]) if(i^par) if(mx.f.f != fdist[i].f-depth[x]) rmx=max(rmx, rdist[i].f-depth[x]);
	// if(x==3) cerr<<mx.f<<' '<<mx.s<<' '<<rmx<<' '<<dist<<' '<<rup<<"\n";
	if(mx.s == 1 && mx.f.f > rmx) {
		// cerr<<x<<' '<<mx.f.s<<' '<<get_dist(x, mx.f.s)<<' '<<rmx<<' '<<dist.s<<'\n';
		// cerr<<x<<' '<<decide(x)<<'\n';
		if(decide(x)) ans[x]=r1.ans[x];
		else ans[x]=r2.ans[x];
		// ans[x]=1;
	}
	set<spi,greater<spi>> ms;
	multiset<pi,greater<pi>> R;
	ms.ins(spi(dist, x)); R.ins(rup);
	for(auto i:v[x]) if(i^par) {
		ms.ins(spi(pi(fdist[i].f-depth[x], fdist[i].s), i));
		R.ins(pi(rdist[i].f-depth[x],rdist[i].s));
	}
	// while(ms.size() > 4) ms.erase(--ms.end());
	// while(R.size() > 4) R.erase(--R.end());
	ll o=ms.size(); ll oR=R.size();
	for(auto i:v[x])if(i^par){
		ms.erase(spi(pi(fdist[i].f-depth[x], fdist[i].s), i));
		if(ms.begin()->s != x) R.erase(R.find(pi(rdist[ms.begin()->s].f-depth[x],rdist[ms.begin()->s].s))); else R.erase(R.find(rup));
		if(*R.begin() == pi(rdist[i].f-depth[x], rdist[i].s)) R.erase(R.begin());
		if((ms.size() >= 2 && ms.begin()->f.f == next(ms.begin())->f.f) || (R.size()&&ms.begin()->f.f <= R.begin()->f)) {
			if(ms.begin()->s != x) R.ins(pi(rdist[ms.begin()->s].f-depth[x],rdist[ms.begin()->s].s));
			else R.ins(rup);
			dfs(i, x, pi(1,x), pi(R.begin()->f + 1, R.begin()->s));
		} else {
			if(ms.begin()->s != x) R.ins(pi(rdist[ms.begin()->s].f-depth[x],rdist[ms.begin()->s].s));
			else R.ins(rup);
			dfs(i, x, pi((ms.begin()->f.f) + 1, ms.begin()->f.s), pi(R.begin()->f + 1, R.begin()->s));
		}
		if(siz(ms) ^ o) ms.ins(spi(pi(fdist[i].f-depth[x],fdist[i].s),i));
		if(siz(R) ^ oR) R.ins(pi(rdist[i].f-depth[x],rdist[i].s));
	}
}*/
struct diam_find {
	vector<ll> dist;
	pi main() {
		dist.resize(n+1, -1);
		dist[1]=0; dfs(1, 1);
		ll r1=1, r2=-1;
		FOR(i,1,n) if(dist[i] > dist[r1]) r1=i;
		r2=r1;
		dist[r1]=0; dfs(r1, r1);
		FOR(i,1,n) if(dist[i] > dist[r2]) r2=i;
		return pi(r1, r2);
	}
	void dfs(ll x,ll p) {
		for(auto i:v[x]) if(i^p) dist[i]=dist[x]+1, dfs(i, x);
	}
} fd;
int main()
{
	// freopen("int", "r", stdin);
	FAST
	cin>>n>>m;
	FOR(i,0,n-2) {
		ll a, b; cin>>a>>b;
		v[a].eb(b), v[b].eb(a);
	}
	FOR(i,1,n) cin>>A[i];
	roots=fd.main(); init(1, 1); t2k();
	r1.root=roots.f, r2.root=roots.s; r1.main(); r2.main();
	// comp(1);
	FOR(i,1,n) {
		// cerr<<i<<": "<<fdist[i]<<"\n";
	}
	// dfs(1, 1, pi(0,1), pi(0,1));
	FOR(i,1,n) cout<<(decide(i)?r1.ans[i]:r2.ans[i])<<"\n";
}
/*
10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10
*/

Compilation message

joi2019_ho_t5.cpp: In function 'int lca(int, int)':
joi2019_ho_t5.cpp:60:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(isp(x,y))return x; if(isp(y,x))return y;
  ^~
joi2019_ho_t5.cpp:60:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(isp(x,y))return x; if(isp(y,x))return y;
                        ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 10104 KB Output is correct
3 Correct 12 ms 10104 KB Output is correct
4 Correct 13 ms 10232 KB Output is correct
5 Correct 13 ms 10104 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 13 ms 10232 KB Output is correct
8 Correct 13 ms 10104 KB Output is correct
9 Correct 13 ms 10104 KB Output is correct
10 Correct 14 ms 10104 KB Output is correct
11 Correct 13 ms 10116 KB Output is correct
12 Correct 13 ms 10104 KB Output is correct
13 Correct 13 ms 10488 KB Output is correct
14 Correct 14 ms 10232 KB Output is correct
15 Correct 13 ms 10232 KB Output is correct
16 Correct 12 ms 10104 KB Output is correct
17 Correct 13 ms 10360 KB Output is correct
18 Correct 13 ms 10360 KB Output is correct
19 Correct 14 ms 10104 KB Output is correct
20 Correct 14 ms 10616 KB Output is correct
21 Correct 13 ms 10232 KB Output is correct
22 Correct 14 ms 10104 KB Output is correct
23 Correct 14 ms 10104 KB Output is correct
24 Correct 14 ms 10104 KB Output is correct
25 Correct 14 ms 10232 KB Output is correct
26 Correct 13 ms 10104 KB Output is correct
27 Correct 14 ms 10488 KB Output is correct
28 Correct 14 ms 10360 KB Output is correct
29 Correct 13 ms 10232 KB Output is correct
30 Correct 13 ms 10104 KB Output is correct
31 Correct 13 ms 10360 KB Output is correct
32 Correct 14 ms 10360 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 28060 KB Output is correct
2 Correct 412 ms 53480 KB Output is correct
3 Correct 68 ms 17272 KB Output is correct
4 Correct 672 ms 41460 KB Output is correct
5 Correct 865 ms 86232 KB Output is correct
6 Correct 823 ms 62788 KB Output is correct
7 Correct 695 ms 41620 KB Output is correct
8 Correct 738 ms 45664 KB Output is correct
9 Correct 694 ms 44196 KB Output is correct
10 Correct 687 ms 44212 KB Output is correct
11 Correct 355 ms 42092 KB Output is correct
12 Correct 785 ms 68460 KB Output is correct
13 Correct 686 ms 62828 KB Output is correct
14 Correct 737 ms 60932 KB Output is correct
15 Correct 326 ms 42020 KB Output is correct
16 Correct 680 ms 72652 KB Output is correct
17 Correct 715 ms 62832 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 35444 KB Output is correct
2 Correct 789 ms 83816 KB Output is correct
3 Correct 75 ms 18476 KB Output is correct
4 Correct 635 ms 42388 KB Output is correct
5 Correct 852 ms 87188 KB Output is correct
6 Correct 765 ms 63648 KB Output is correct
7 Correct 586 ms 42360 KB Output is correct
8 Correct 748 ms 50740 KB Output is correct
9 Correct 775 ms 47892 KB Output is correct
10 Correct 732 ms 45524 KB Output is correct
11 Correct 577 ms 42716 KB Output is correct
12 Correct 907 ms 77556 KB Output is correct
13 Correct 703 ms 60608 KB Output is correct
14 Correct 874 ms 61144 KB Output is correct
15 Correct 329 ms 43120 KB Output is correct
16 Correct 681 ms 73428 KB Output is correct
17 Correct 708 ms 64008 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 10104 KB Output is correct
3 Correct 12 ms 10104 KB Output is correct
4 Correct 13 ms 10232 KB Output is correct
5 Correct 13 ms 10104 KB Output is correct
6 Correct 13 ms 10488 KB Output is correct
7 Correct 13 ms 10232 KB Output is correct
8 Correct 13 ms 10104 KB Output is correct
9 Correct 13 ms 10104 KB Output is correct
10 Correct 14 ms 10104 KB Output is correct
11 Correct 13 ms 10116 KB Output is correct
12 Correct 13 ms 10104 KB Output is correct
13 Correct 13 ms 10488 KB Output is correct
14 Correct 14 ms 10232 KB Output is correct
15 Correct 13 ms 10232 KB Output is correct
16 Correct 12 ms 10104 KB Output is correct
17 Correct 13 ms 10360 KB Output is correct
18 Correct 13 ms 10360 KB Output is correct
19 Correct 14 ms 10104 KB Output is correct
20 Correct 14 ms 10616 KB Output is correct
21 Correct 13 ms 10232 KB Output is correct
22 Correct 14 ms 10104 KB Output is correct
23 Correct 14 ms 10104 KB Output is correct
24 Correct 14 ms 10104 KB Output is correct
25 Correct 14 ms 10232 KB Output is correct
26 Correct 13 ms 10104 KB Output is correct
27 Correct 14 ms 10488 KB Output is correct
28 Correct 14 ms 10360 KB Output is correct
29 Correct 13 ms 10232 KB Output is correct
30 Correct 13 ms 10104 KB Output is correct
31 Correct 13 ms 10360 KB Output is correct
32 Correct 14 ms 10360 KB Output is correct
33 Correct 293 ms 28060 KB Output is correct
34 Correct 412 ms 53480 KB Output is correct
35 Correct 68 ms 17272 KB Output is correct
36 Correct 672 ms 41460 KB Output is correct
37 Correct 865 ms 86232 KB Output is correct
38 Correct 823 ms 62788 KB Output is correct
39 Correct 695 ms 41620 KB Output is correct
40 Correct 738 ms 45664 KB Output is correct
41 Correct 694 ms 44196 KB Output is correct
42 Correct 687 ms 44212 KB Output is correct
43 Correct 355 ms 42092 KB Output is correct
44 Correct 785 ms 68460 KB Output is correct
45 Correct 686 ms 62828 KB Output is correct
46 Correct 737 ms 60932 KB Output is correct
47 Correct 326 ms 42020 KB Output is correct
48 Correct 680 ms 72652 KB Output is correct
49 Correct 715 ms 62832 KB Output is correct
50 Correct 462 ms 35444 KB Output is correct
51 Correct 789 ms 83816 KB Output is correct
52 Correct 75 ms 18476 KB Output is correct
53 Correct 635 ms 42388 KB Output is correct
54 Correct 852 ms 87188 KB Output is correct
55 Correct 765 ms 63648 KB Output is correct
56 Correct 586 ms 42360 KB Output is correct
57 Correct 748 ms 50740 KB Output is correct
58 Correct 775 ms 47892 KB Output is correct
59 Correct 732 ms 45524 KB Output is correct
60 Correct 577 ms 42716 KB Output is correct
61 Correct 907 ms 77556 KB Output is correct
62 Correct 703 ms 60608 KB Output is correct
63 Correct 874 ms 61144 KB Output is correct
64 Correct 329 ms 43120 KB Output is correct
65 Correct 681 ms 73428 KB Output is correct
66 Correct 708 ms 64008 KB Output is correct
67 Correct 58 ms 14200 KB Output is correct
68 Correct 282 ms 43372 KB Output is correct
69 Correct 447 ms 42996 KB Output is correct
70 Correct 616 ms 41464 KB Output is correct
71 Correct 1024 ms 86376 KB Output is correct
72 Correct 773 ms 62708 KB Output is correct
73 Correct 561 ms 41464 KB Output is correct
74 Correct 752 ms 49368 KB Output is correct
75 Correct 681 ms 45080 KB Output is correct
76 Correct 723 ms 44608 KB Output is correct
77 Correct 440 ms 41840 KB Output is correct
78 Correct 854 ms 72940 KB Output is correct
79 Correct 675 ms 67924 KB Output is correct
80 Correct 762 ms 58548 KB Output is correct
81 Correct 313 ms 41688 KB Output is correct
82 Correct 661 ms 72580 KB Output is correct
83 Correct 696 ms 62756 KB Output is correct
84 Correct 607 ms 41724 KB Output is correct
85 Correct 907 ms 86548 KB Output is correct
86 Correct 789 ms 62976 KB Output is correct
87 Correct 601 ms 41852 KB Output is correct
88 Correct 758 ms 50280 KB Output is correct
89 Correct 693 ms 46072 KB Output is correct
90 Correct 851 ms 45176 KB Output is correct
91 Correct 448 ms 42092 KB Output is correct
92 Correct 904 ms 85012 KB Output is correct
93 Correct 734 ms 56440 KB Output is correct
94 Correct 706 ms 52524 KB Output is correct
95 Correct 313 ms 42308 KB Output is correct
96 Correct 689 ms 72672 KB Output is correct
97 Correct 728 ms 63212 KB Output is correct
98 Correct 771 ms 42420 KB Output is correct
99 Correct 964 ms 86924 KB Output is correct
100 Correct 927 ms 63708 KB Output is correct
101 Correct 574 ms 42264 KB Output is correct
102 Correct 828 ms 48856 KB Output is correct
103 Correct 695 ms 46200 KB Output is correct
104 Correct 680 ms 45388 KB Output is correct
105 Correct 429 ms 42608 KB Output is correct
106 Correct 803 ms 66200 KB Output is correct
107 Correct 731 ms 67812 KB Output is correct
108 Correct 736 ms 55020 KB Output is correct
109 Correct 309 ms 42864 KB Output is correct
110 Correct 654 ms 73112 KB Output is correct
111 Correct 763 ms 63880 KB Output is correct