oj.uz

Submission #1099838

# Submission time Handle Problem Language Result Execution time Memory
1099838 2024-10-12T05:33:19 Z model_code Tree (IOI24_tree) C++17
23 / 100
 2000 ms 68616 KB 
// time_limit/mruxim-qn2.cpp

#include<bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)
#define fer(i, a, b) for(int i = (int)(a), i##__b = (int)(b); i < i##__b; ++i)
#define rof(i, b, a) for(int i = (int)(b), i##__a = (int)(a); i-- > i##__a; )
#define sz(x) (int((x).size()))
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
//#define endl '\n'

template<class P, class Q> inline void smin(P &a, Q b) { if (b < a) a = b; }
template<class P, class Q> inline void smax(P &a, Q b) { if (a < b) a = b; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;

////////////////////////////////////////////////////////////////////////////////

const int maxn = 300'000 + 100;

int n;
vector<int> p, w;
vector<int> ch[maxn];
ll sum[maxn];
set<pii> st[maxn];

void init(vector<int> _p, vector<int> _w) {
	p = _p, w = _w;
	n = sz(p);

	fer(i, 1, n) ch[p[i]].pb(i);
}

void dfs_rem(int u, set<pii> &ss) {
	if(!ss.erase(pii(w[u], u))) return;
	for(int v: ch[u]) dfs_rem(v, ss);
}

ll query(int l, int r) {
	fill(sum, sum+n, 0);
	rep(i, n) st[i].clear();

	ll ans = 0;
	rof(i, n, 0) {
		if(sz(ch[i]) == 0) {
			sum[i] = l;
			ans += l * (ll)w[i];
		} else {
			int u = i;
			if(sum[u] - l > 0) st[u].insert({w[u], u});
			while(r < sum[u]) {
				int v = (*st[u].begin()).second;
				ll d = sum[u] - r;
				int g = -1;
				for(int x = v; x != p[u]; x = p[x]) smin(d, sum[x] - l), (d == sum[x] - l && (g = x));
				for(int x = v; x != p[u]; x = p[x]) sum[x] -= d;
				ans += d * (ll)w[v];
				if(g != -1) dfs_rem(g, st[u]);
			}
		}

		if(i) {
			sum[p[i]] += sum[i];
			if(sz(st[p[i]]) < sz(st[i])) st[p[i]].swap(st[i]);
			st[p[i]].insert(all(st[i]));
		}
	}

	return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 37476 KB Output is correct
2 Correct 234 ms 37112 KB Output is correct
3 Correct 130 ms 33564 KB Output is correct
4 Correct 840 ms 51364 KB Output is correct
5 Correct 853 ms 52444 KB Output is correct
6 Correct 676 ms 50532 KB Output is correct
7 Correct 755 ms 50480 KB Output is correct
8 Correct 1020 ms 51968 KB Output is correct
9 Correct 1618 ms 68616 KB Output is correct
10 Correct 47 ms 29904 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23900 KB Output is correct
2 Correct 9 ms 23896 KB Output is correct
3 Correct 6 ms 24060 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 6 ms 23896 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Correct 8 ms 24156 KB Output is correct
8 Correct 5 ms 23900 KB Output is correct

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23900 KB Output is correct
2 Correct 9 ms 23896 KB Output is correct
3 Correct 6 ms 24060 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 6 ms 23896 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Correct 8 ms 24156 KB Output is correct
8 Correct 5 ms 23900 KB Output is correct
9 Execution timed out 2062 ms 29924 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 38148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 38148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 34836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 231 ms 37476 KB Output is correct
3 Correct 234 ms 37112 KB Output is correct
4 Correct 130 ms 33564 KB Output is correct
5 Correct 840 ms 51364 KB Output is correct
6 Correct 853 ms 52444 KB Output is correct
7 Correct 676 ms 50532 KB Output is correct
8 Correct 755 ms 50480 KB Output is correct
9 Correct 1020 ms 51968 KB Output is correct
10 Correct 1618 ms 68616 KB Output is correct
11 Correct 47 ms 29904 KB Output is correct
12 Correct 23 ms 23900 KB Output is correct
13 Correct 9 ms 23896 KB Output is correct
14 Correct 6 ms 24060 KB Output is correct
15 Correct 6 ms 23900 KB Output is correct
16 Correct 6 ms 23896 KB Output is correct
17 Correct 6 ms 23900 KB Output is correct
18 Correct 8 ms 24156 KB Output is correct
19 Correct 5 ms 23900 KB Output is correct
20 Execution timed out 2062 ms 29924 KB Time limit exceeded
21 Halted 0 ms 0 KB -