oj.uz

Submission #729985

# Submission time Handle Problem Language Result Execution time Memory
729985 2023-04-25T02:36:34 Z pavement Unique Cities (JOI19_ho_t5) C++17
64 / 100
 824 ms 114476 KB 
#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;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, M, lon[200005], ans_st[200005], ans_ed[200005], lon_st[200005], lon_ed[200005], dist_st[200005], dist_ed[200005];
ii m = mp(-1, -1);
vector<int> adj[200005];

struct node {
	node *left, *right;
	int S, E, pv;
	ii val;
	void combine() {
		if (S == E) return;
		if (left->val.first == right->val.first) val = mp(left->val.first, left->val.second + right->val.second);
		else val = min(left->val, right->val);
	}
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val = mp(0, 1);
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		combine();
	}
	void prop() {
		if (S == E || !pv) return;
		left->val.first += pv;
		left->pv += pv;
		right->val.first += pv;
		right->pv += pv;
		pv = 0;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		combine();
	}
	ii qry(int l, int r) {
		if (l > E || r < S) return mp((int)1e16, 0);
		if (l <= S && E <= r) return val;
		prop();
		auto lq = left->qry(l, r), rq = right->qry(l, r);
		if (lq.first == rq.first) return mp(lq.first, lq.second + rq.second);
		else return min(lq, rq);
	}
} *root;

void dfs(int n, int e = -1, int d = 0) {
	m = max(m, mp(d, n));
	for (auto u : adj[n]) if (u != e) {
		dfs(u, n, d + 1);
	}
}

void init(int n, int lon[], int dist[], int e = -1) {
	for (auto u : adj[n]) if (u != e) {
		dist[u] = dist[n] + 1;
		init(u, lon, dist, n);
		lon[n] = max(lon[n], lon[u]);
	}
	lon[n]++;
}

void get_ans(int n, int ans[], int lon[], int e = -1, int d = 0) {
	root->upd(d - lon[n] + 1, d - 1, 1);
	ans[n] = root->qry(0, d).second;
	root->upd(d - lon[n] + 1, d - 1, -1);
	multiset<int> m;
	for (auto u : adj[n]) if (u != e) {
		m.insert(lon[u]);
	}
	for (auto u : adj[n]) if (u != e) {
		m.erase(m.find(lon[u]));
		int x = (m.empty() ? 0ll : *m.rbegin());
		root->upd(d - x, d - 1, 1);
		get_ans(u, ans, lon, n, d + 1);
		root->upd(d - x, d - 1, -1);
		m.insert(lon[u]);
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1, u, v; i < N; i++) {
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	int st = m.second;
	m = mp(-1, -1);
	dfs(st);
	int ed = m.second;
	root = new node(0, N - 1);
	init(st, lon_st, dist_st);
	get_ans(st, ans_st, lon_st);
	root = new node(0, N - 1);
	init(ed, lon_ed, dist_ed);
	get_ans(ed, ans_ed, lon_ed);
	for (int i = 1; i <= N; i++) {
		int x;
		if (dist_st[i] <= dist_ed[i]) {
			x = ans_ed[i] - 1;
		} else {
			x = ans_st[i] - 1;
		}
		if (M == 1) cout << !!x << '\n';
		else cout << x << '\n';
	}
}

Compilation message

joi2019_ho_t5.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main() {
      | ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 6 ms 5716 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 334 ms 43796 KB Output is correct
2 Correct 419 ms 67984 KB Output is correct
3 Correct 78 ms 17688 KB Output is correct
4 Correct 667 ms 74912 KB Output is correct
5 Correct 790 ms 114476 KB Output is correct
6 Correct 742 ms 94380 KB Output is correct
7 Correct 668 ms 76616 KB Output is correct
8 Correct 732 ms 80336 KB Output is correct
9 Correct 712 ms 78984 KB Output is correct
10 Correct 702 ms 78616 KB Output is correct
11 Correct 538 ms 84188 KB Output is correct
12 Correct 824 ms 102724 KB Output is correct
13 Correct 743 ms 97984 KB Output is correct
14 Correct 756 ms 95652 KB Output is correct
15 Correct 614 ms 84740 KB Output is correct
16 Correct 719 ms 104848 KB Output is correct
17 Correct 733 ms 96988 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 58152 KB Output is correct
2 Correct 728 ms 108080 KB Output is correct
3 Correct 81 ms 18892 KB Output is correct
4 Correct 651 ms 72232 KB Output is correct
5 Correct 796 ms 112748 KB Output is correct
6 Correct 741 ms 92080 KB Output is correct
7 Correct 631 ms 73492 KB Output is correct
8 Correct 757 ms 82640 KB Output is correct
9 Correct 709 ms 79552 KB Output is correct
10 Correct 686 ms 76620 KB Output is correct
11 Correct 600 ms 76992 KB Output is correct
12 Correct 797 ms 106560 KB Output is correct
13 Correct 743 ms 93136 KB Output is correct
14 Correct 746 ms 92332 KB Output is correct
15 Correct 605 ms 82096 KB Output is correct
16 Correct 712 ms 102412 KB Output is correct
17 Correct 735 ms 94444 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 6 ms 5716 KB Output isn't correct
3 Halted 0 ms 0 KB -