oj.uz

Submission #1099836

# Submission time Handle Problem Language Result Execution time Memory
1099836 2024-10-12T05:32:56 Z model_code Tree (IOI24_tree) C++17
10 / 100
 2000 ms 31688 KB 
// time_limit/mruxim-qwinc.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);
}

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];
		}
		
		ll d = max(0ll, sum[i] - r);
		ans += d * (ll)w[i];
		sum[i] -= d;

		if(i) sum[p[i]] += sum[i];
	}

	return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21336 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 30316 KB Output is correct
2 Correct 54 ms 30288 KB Output is correct
3 Correct 62 ms 28240 KB Output is correct
4 Correct 88 ms 30036 KB Output is correct
5 Correct 94 ms 30036 KB Output is correct
6 Correct 63 ms 30044 KB Output is correct
7 Correct 73 ms 30168 KB Output is correct
8 Correct 64 ms 30032 KB Output is correct
9 Correct 72 ms 29304 KB Output is correct
10 Correct 46 ms 27340 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 21596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 21596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 31688 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 2039 ms 31688 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 2045 ms 30288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21336 KB Output is correct
2 Correct 61 ms 30316 KB Output is correct
3 Correct 54 ms 30288 KB Output is correct
4 Correct 62 ms 28240 KB Output is correct
5 Correct 88 ms 30036 KB Output is correct
6 Correct 94 ms 30036 KB Output is correct
7 Correct 63 ms 30044 KB Output is correct
8 Correct 73 ms 30168 KB Output is correct
9 Correct 64 ms 30032 KB Output is correct
10 Correct 72 ms 29304 KB Output is correct
11 Correct 46 ms 27340 KB Output is correct
12 Incorrect 9 ms 21596 KB Output isn't correct
13 Halted 0 ms 0 KB -