oj.uz

Submission #388573

# Submission time Handle Problem Language Result Execution time Memory
388573 2021-04-12T07:17:44 Z Return_0 Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 284 ms 33444 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#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 int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1 << 30) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 7e4 + 7;

ll par [N], L [N], R [N], deg [N], ans [N], n, m;
vector <ll> adj [N], vec;
set <ll> Mn [N], Mx [N];
bool mark [N], SIK [N];
vector <pll> aj [N];
set <pll> st;

void dfs (cl &v = 1, cl &pr = 0) {
	par[v] = pr; L[v] = -inf, R[v] = inf; ans[v] = -1;
	for (auto &u : adj[v]) if (u != pr) {
		dfs(u, v);
		if (SZ(Mx[v]) < SZ(Mx[u])) Mx[v].swap(Mx[u]);
		for (auto &x : Mx[u]) {
			if (Mx[v].count(x)) Mx[v].erase(x);
			else Mx[v].insert(x);
		}
		if (SZ(Mn[v]) < SZ(Mn[u])) Mn[v].swap(Mn[u]);
		for (auto &x : Mn[u]) {
			if (Mn[v].count(x)) Mn[v].erase(x);
			else Mn[v].insert(x);
		}
	}
	if (!Mx[v].empty()) R[v] = *Mx[v].begin();
	if (!Mn[v].empty()) L[v] = *Mn[v].rbegin();
}

void DFS () {
	for (ll i = 0; i < m; i++) st.insert({deg[i] = SZ(aj[i]), i});
	for (ll x; !st.empty();) {
		x = st.begin()->sc; st.erase(st.begin());
		for (auto [y, v] : aj[x]) if (!mark[v]) {
			mark[v] = SIK[x] = 1;
			ans[v] = x;
			if (!SIK[y]) st.erase({deg[y], y}), st.insert({--deg[y], y});
			break;
		}
	}
}

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n;
	for (ll i = 1, v, u; i < n; i++) {
		cin>> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	cin>> m;
	for (ll i = 0, v, u, x; i < m; i++) {
		char tp; cin>> tp >> v >> u >> x;
		vec.push_back(x);
		if (tp == 'm') Mn[v].insert(x), Mn[u].insert(x);
		else Mx[v].insert(x), Mx[u].insert(x);
	}

	dfs();
	sort(All(vec));

	for (ll v = 2, l, r; v <= n; v++) {
		l = L[v], r = R[v];
		if (0 <= l) l = lower_bound(All(vec), l) - vec.begin(); 
		if (r < inf) r = lower_bound(All(vec), r) - vec.begin();
		if (0 <= l && r < inf) { aj[l].push_back({r, v}); aj[r].push_back({l, v}); }
		else if (0 <= l) aj[l].push_back({l, v}), aj[l].push_back({l, v});
		else if (r < inf) aj[r].push_back({r, v}), aj[r].push_back({r, v});
	}

	DFS();
	for (ll v = 2; v <= n; v++) {
		if (!~ans[v]) ans[v] = max(0, L[v]);
		else ans[v] = vec[ans[v]];
		cout<< v << ' ' << par[v] << ' ' << ans[v] << '\n';
	}

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 0
M 2 3 100

5
1 2
2 3
3 4
4 5
2
M 2 4 9
m 2 3 3

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10188 KB Output is correct
2 Correct 6 ms 10188 KB Output is correct
3 Correct 6 ms 10188 KB Output is correct
4 Correct 8 ms 10188 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 30812 KB Output is correct
2 Correct 232 ms 32364 KB Output is correct
3 Correct 221 ms 27812 KB Output is correct
4 Correct 229 ms 31408 KB Output is correct
5 Correct 229 ms 29536 KB Output is correct
6 Correct 237 ms 28144 KB Output is correct
7 Correct 247 ms 24712 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 19116 KB Output is correct
2 Correct 137 ms 19200 KB Output is correct
3 Correct 126 ms 20812 KB Output is correct
4 Correct 125 ms 22224 KB Output is correct
5 Correct 139 ms 19896 KB Output is correct
6 Correct 153 ms 20616 KB Output is correct
7 Correct 142 ms 19528 KB Output is correct
8 Correct 148 ms 19396 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10188 KB Output is correct
2 Correct 6 ms 10188 KB Output is correct
3 Correct 6 ms 10188 KB Output is correct
4 Correct 8 ms 10188 KB Output is correct
5 Correct 246 ms 30812 KB Output is correct
6 Correct 232 ms 32364 KB Output is correct
7 Correct 221 ms 27812 KB Output is correct
8 Correct 229 ms 31408 KB Output is correct
9 Correct 229 ms 29536 KB Output is correct
10 Correct 237 ms 28144 KB Output is correct
11 Correct 247 ms 24712 KB Output is correct
12 Correct 118 ms 19116 KB Output is correct
13 Correct 137 ms 19200 KB Output is correct
14 Correct 126 ms 20812 KB Output is correct
15 Correct 125 ms 22224 KB Output is correct
16 Correct 139 ms 19896 KB Output is correct
17 Correct 153 ms 20616 KB Output is correct
18 Correct 142 ms 19528 KB Output is correct
19 Correct 148 ms 19396 KB Output is correct
20 Correct 279 ms 33444 KB Output is correct
21 Correct 255 ms 31556 KB Output is correct
22 Correct 257 ms 33092 KB Output is correct
23 Correct 250 ms 30952 KB Output is correct
24 Correct 270 ms 31216 KB Output is correct
25 Correct 276 ms 32756 KB Output is correct
26 Correct 259 ms 30788 KB Output is correct
27 Correct 284 ms 31240 KB Output is correct
28 Correct 279 ms 28524 KB Output is correct
29 Correct 269 ms 28916 KB Output is correct
30 Correct 214 ms 27584 KB Output is correct
31 Correct 229 ms 28496 KB Output is correct
32 Correct 258 ms 28932 KB Output is correct
33 Correct 266 ms 30224 KB Output is correct
34 Correct 272 ms 30488 KB Output is correct
35 Correct 231 ms 27584 KB Output is correct