oj.uz

Submission #388571

# Submission time Handle Problem Language Result Execution time Memory
388571 2021-04-12T07:14:39 Z Return_0 Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 294 ms 35768 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 <pll> aj [N];
vector <ll> adj [N], vec;
set <ll> Mn [N], Mx [N];
set <pll> st;
bool mark [N];

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] = 1;
			ans[v] = x;
			if (x != 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)); vec.resize(unique(All(vec)) - vec.begin()); m = SZ(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 8 ms 10124 KB Output is correct
4 Correct 7 ms 10188 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 30828 KB Output is correct
2 Correct 239 ms 34692 KB Output is correct
3 Correct 213 ms 29796 KB Output is correct
4 Correct 218 ms 33708 KB Output is correct
5 Correct 213 ms 31608 KB Output is correct
6 Correct 203 ms 30524 KB Output is correct
7 Correct 205 ms 26948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 19016 KB Output is correct
2 Correct 110 ms 19188 KB Output is correct
3 Correct 104 ms 20804 KB Output is correct
4 Correct 107 ms 23412 KB Output is correct
5 Correct 148 ms 21444 KB Output is correct
6 Correct 131 ms 22084 KB Output is correct
7 Correct 130 ms 21188 KB Output is correct
8 Correct 131 ms 20768 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 8 ms 10124 KB Output is correct
4 Correct 7 ms 10188 KB Output is correct
5 Correct 212 ms 30828 KB Output is correct
6 Correct 239 ms 34692 KB Output is correct
7 Correct 213 ms 29796 KB Output is correct
8 Correct 218 ms 33708 KB Output is correct
9 Correct 213 ms 31608 KB Output is correct
10 Correct 203 ms 30524 KB Output is correct
11 Correct 205 ms 26948 KB Output is correct
12 Correct 111 ms 19016 KB Output is correct
13 Correct 110 ms 19188 KB Output is correct
14 Correct 104 ms 20804 KB Output is correct
15 Correct 107 ms 23412 KB Output is correct
16 Correct 148 ms 21444 KB Output is correct
17 Correct 131 ms 22084 KB Output is correct
18 Correct 130 ms 21188 KB Output is correct
19 Correct 131 ms 20768 KB Output is correct
20 Correct 269 ms 35768 KB Output is correct
21 Correct 243 ms 33596 KB Output is correct
22 Correct 259 ms 35136 KB Output is correct
23 Correct 243 ms 33044 KB Output is correct
24 Correct 259 ms 33604 KB Output is correct
25 Correct 290 ms 35164 KB Output is correct
26 Correct 246 ms 32956 KB Output is correct
27 Correct 274 ms 33592 KB Output is correct
28 Correct 248 ms 30928 KB Output is correct
29 Correct 255 ms 31168 KB Output is correct
30 Correct 224 ms 29624 KB Output is correct
31 Correct 261 ms 30532 KB Output is correct
32 Correct 269 ms 31408 KB Output is correct
33 Correct 268 ms 32448 KB Output is correct
34 Correct 294 ms 32596 KB Output is correct
35 Correct 254 ms 29732 KB Output is correct