oj.uz

Submission #519449

# Submission time Handle Problem Language Result Execution time Memory
519449 2022-01-26T11:45:04 Z AriaH Unique Cities (JOI19_ho_t5) C++14
36 / 100
 2000 ms 192216 KB 
/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef __int128 INT;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

template < typename T > using Tree = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, C[N], H[N], dp[N], mark[N], S[N], Ans[N];

set < pii > st;

vector < int > G[N];

void pre(int v, int P = 0)
{
	H[v] = H[P] + 1;
	dp[v] = 1;
	for(auto u : G[v])
	{
		if(u == P) continue;
		pre(u, v);
		dp[v] = max(dp[v], dp[u] + 1);
	}
}

bool cmp(int i, int j)
{
	return dp[i] < dp[j];
}

void dfs(int v, int P, int tp)
{
	/*printf("v = %d P = %d\n", v, P);
	for(auto x : st)
	{
		printf("%d %d\n", x.F, x.S);
	}
	printf("\n");
	*/
	vector < pii > hist;
	sort(all(G[v]), cmp);
	int Mx1 = 0, Mx2 = 0, id1 = -1;
	for(auto u : G[v])
	{
		if(u == P) continue;
		if(dp[u] > Mx1)
		{
			Mx2 = Mx1;
			Mx1 = dp[u];
			id1 = u;
		}
		else if(dp[u] > Mx2)
		{
			Mx2 = dp[u];
		}
	}
	while(SZ(st))
	{
		pii cu = *st.begin();
		cu.F = -cu.F;
		if(cu.F >= H[v] - Mx1)
		{
			hist.push_back(cu);
			st.erase(st.begin());
			mark[cu.S] = 0;
		}
		else
		{
			break;
		}
	}
	/*printf("Mx1 = %d Mx2 = %d after : \n", Mx1, Mx2);
	for(auto x : st)
	{
		printf("%d %d\n", x.F, x.S);
	}
	printf("\n");
	*/
	if(S[v] == tp) Ans[v] += SZ(st);
	if(!mark[C[v]])
	{
		mark[C[v]] = 1;
		st.insert({-H[v], C[v]});
	}
	for(auto u : G[v])
	{
		if(u == P || u == id1) continue;
		dfs(u, v, tp);
	}
	if(st.count({-H[v], C[v]}))
	{
		st.erase({-H[v], C[v]});
		mark[C[v]] = 0;
	}
	while(SZ(hist))
	{
		pii cu = hist.back();
		if(cu.F >= H[v] - Mx2)
		{
			break;
		}
		mark[cu.S] = 1;
		st.insert({-cu.F, cu.S});
		hist.pop_back();
	}
	if(!mark[C[v]])
	{
		mark[C[v]] = 1;
		st.insert({-H[v], C[v]});
	}
	if(id1 != -1)
	{
		dfs(id1, v, tp);
	}
	if(st.count({-H[v], C[v]}))
	{
		st.erase({-H[v], C[v]});
		mark[C[v]] = 0;
	}
	while(SZ(hist))
	{
		pii cu = hist.back();
		hist.pop_back();
		st.insert({-cu.F, cu.S});
		mark[cu.S] = 1;
	}
}

int fir[N], sec[N];

int main()
{
	fast_io;
	cin >> n >> m;
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i = 1; i <= n; i ++)
	{
		cin >> C[i];
	}
	pre(1, 0);
	int L = 0, R = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(H[i] > H[L]) L = i;
	}
	pre(L, 0);
	///printf("L = %d\n", L);
	for(int i = 1; i <= n; i ++)
	{
		fir[i] = H[i];
		if(H[i] > H[R]) R = i;
		///printf("i = %d H = %d dp = %d\n", i, H[i], dp[i]);
	}
	pre(R, 0);
	for(int i = 1; i <= n; i ++)
	{
		sec[i] = H[i];
		if(fir[i] > sec[i])
		{
			S[i] = 0;
		}
		else
		{
			S[i] = 1;
		}
	}
	pre(L, 0);
	///printf("R = %d\n", R);
	dfs(L, 0, 0);
	st.clear();
	memset(mark, 0, sizeof mark);
	pre(R, 0);
	for(int i = 1; i <= n; i ++)
	{
		///printf("i = %d H = %d dp = %d\n", i, H[i], dp[i]);
	}
	dfs(R, 0, 1);
	for(int i = 1; i <= n; i ++)
	{
		cout << Ans[i] << "\n";
	}

	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27720 KB Output is correct
2 Correct 18 ms 27880 KB Output is correct
3 Correct 54 ms 29912 KB Output is correct
4 Correct 44 ms 29160 KB Output is correct
5 Correct 17 ms 27852 KB Output is correct
6 Correct 18 ms 28236 KB Output is correct
7 Correct 17 ms 27980 KB Output is correct
8 Correct 18 ms 27816 KB Output is correct
9 Correct 18 ms 27852 KB Output is correct
10 Correct 17 ms 27916 KB Output is correct
11 Correct 18 ms 27916 KB Output is correct
12 Correct 17 ms 27852 KB Output is correct
13 Correct 22 ms 28176 KB Output is correct
14 Correct 21 ms 27960 KB Output is correct
15 Correct 18 ms 27980 KB Output is correct
16 Correct 17 ms 27924 KB Output is correct
17 Correct 17 ms 28072 KB Output is correct
18 Correct 17 ms 28052 KB Output is correct
19 Correct 19 ms 28020 KB Output is correct
20 Correct 159 ms 36260 KB Output is correct
21 Correct 79 ms 29900 KB Output is correct
22 Correct 18 ms 27920 KB Output is correct
23 Correct 18 ms 27920 KB Output is correct
24 Correct 18 ms 27928 KB Output is correct
25 Correct 18 ms 27920 KB Output is correct
26 Correct 17 ms 27920 KB Output is correct
27 Correct 95 ms 31880 KB Output is correct
28 Correct 68 ms 30836 KB Output is correct
29 Correct 40 ms 28996 KB Output is correct
30 Correct 17 ms 27852 KB Output is correct
31 Correct 43 ms 29504 KB Output is correct
32 Correct 58 ms 29824 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 35544 KB Output is correct
2 Correct 208 ms 54216 KB Output is correct
3 Correct 42 ms 32120 KB Output is correct
4 Correct 392 ms 42900 KB Output is correct
5 Correct 437 ms 74036 KB Output is correct
6 Correct 487 ms 59376 KB Output is correct
7 Correct 323 ms 43036 KB Output is correct
8 Correct 350 ms 46024 KB Output is correct
9 Correct 360 ms 45124 KB Output is correct
10 Correct 332 ms 44996 KB Output is correct
11 Correct 174 ms 43596 KB Output is correct
12 Correct 403 ms 62308 KB Output is correct
13 Correct 369 ms 58100 KB Output is correct
14 Correct 377 ms 57940 KB Output is correct
15 Correct 159 ms 43460 KB Output is correct
16 Correct 354 ms 63892 KB Output is correct
17 Correct 370 ms 59380 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 38228 KB Output is correct
2 Execution timed out 2066 ms 192216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27720 KB Output is correct
2 Correct 18 ms 27880 KB Output is correct
3 Correct 54 ms 29912 KB Output is correct
4 Correct 44 ms 29160 KB Output is correct
5 Correct 17 ms 27852 KB Output is correct
6 Correct 18 ms 28236 KB Output is correct
7 Correct 17 ms 27980 KB Output is correct
8 Correct 18 ms 27816 KB Output is correct
9 Correct 18 ms 27852 KB Output is correct
10 Correct 17 ms 27916 KB Output is correct
11 Correct 18 ms 27916 KB Output is correct
12 Correct 17 ms 27852 KB Output is correct
13 Correct 22 ms 28176 KB Output is correct
14 Correct 21 ms 27960 KB Output is correct
15 Correct 18 ms 27980 KB Output is correct
16 Correct 17 ms 27924 KB Output is correct
17 Correct 17 ms 28072 KB Output is correct
18 Correct 17 ms 28052 KB Output is correct
19 Correct 19 ms 28020 KB Output is correct
20 Correct 159 ms 36260 KB Output is correct
21 Correct 79 ms 29900 KB Output is correct
22 Correct 18 ms 27920 KB Output is correct
23 Correct 18 ms 27920 KB Output is correct
24 Correct 18 ms 27928 KB Output is correct
25 Correct 18 ms 27920 KB Output is correct
26 Correct 17 ms 27920 KB Output is correct
27 Correct 95 ms 31880 KB Output is correct
28 Correct 68 ms 30836 KB Output is correct
29 Correct 40 ms 28996 KB Output is correct
30 Correct 17 ms 27852 KB Output is correct
31 Correct 43 ms 29504 KB Output is correct
32 Correct 58 ms 29824 KB Output is correct
33 Correct 171 ms 35544 KB Output is correct
34 Correct 208 ms 54216 KB Output is correct
35 Correct 42 ms 32120 KB Output is correct
36 Correct 392 ms 42900 KB Output is correct
37 Correct 437 ms 74036 KB Output is correct
38 Correct 487 ms 59376 KB Output is correct
39 Correct 323 ms 43036 KB Output is correct
40 Correct 350 ms 46024 KB Output is correct
41 Correct 360 ms 45124 KB Output is correct
42 Correct 332 ms 44996 KB Output is correct
43 Correct 174 ms 43596 KB Output is correct
44 Correct 403 ms 62308 KB Output is correct
45 Correct 369 ms 58100 KB Output is correct
46 Correct 377 ms 57940 KB Output is correct
47 Correct 159 ms 43460 KB Output is correct
48 Correct 354 ms 63892 KB Output is correct
49 Correct 370 ms 59380 KB Output is correct
50 Correct 314 ms 38228 KB Output is correct
51 Execution timed out 2066 ms 192216 KB Time limit exceeded
52 Halted 0 ms 0 KB -