oj.uz

Submission #1099831

# Submission time Handle Problem Language Result Execution time Memory
1099831 2024-10-12T05:31:57 Z model_code Tree (IOI24_tree) C++17
18 / 100
 54 ms 8256 KB 
// incorrect/mruxim-w01.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;
int cnt[maxn];
int leaves_cnt[maxn];
int leaves_sum;
vector<int> cnts;
vector<int> psum;

void init(vector<int> _p, vector<int> _w) {
	p = _p, w = _w;
	n = sz(p);
	
	fer(i, 1, n) cnt[p[i]]++;

	leaves_sum = 0;
	rof(i, n, 0) {
		leaves_sum += (cnt[i] == 0 ? w[i] : 0);
		leaves_cnt[i] += (cnt[i] == 0 || w[i] == 0 ? 1 : 0);
		if(i > 0 && w[p[i]] == 1)
			leaves_cnt[p[i]] += leaves_cnt[i];
		else if(w[i] == 1)
			cnts.pb(leaves_cnt[i]);
	}

	sort(all(cnts));

	psum.assign(sz(cnts) + 1, 0);
	partial_sum(all(cnts), psum.begin() + 1);
	
}

ll query(int l, int r) {
	int pos = upper_bound(all(cnts), r / l) - cnts.begin();
	return leaves_sum * (ll)l + (psum.back() - psum[pos]) * (ll)l - (sz(psum) - 1 - pos) * (ll)r;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7612 KB Output is correct
2 Correct 44 ms 7716 KB Output is correct
3 Correct 41 ms 7732 KB Output is correct
4 Correct 41 ms 7732 KB Output is correct
5 Correct 41 ms 7728 KB Output is correct
6 Correct 43 ms 7604 KB Output is correct
7 Correct 46 ms 7876 KB Output is correct
8 Correct 38 ms 7116 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7612 KB Output is correct
2 Correct 44 ms 7716 KB Output is correct
3 Correct 41 ms 7732 KB Output is correct
4 Correct 41 ms 7732 KB Output is correct
5 Correct 41 ms 7728 KB Output is correct
6 Correct 43 ms 7604 KB Output is correct
7 Correct 46 ms 7876 KB Output is correct
8 Correct 38 ms 7116 KB Output is correct
9 Correct 47 ms 8144 KB Output is correct
10 Correct 52 ms 8112 KB Output is correct
11 Correct 52 ms 8112 KB Output is correct
12 Correct 54 ms 8232 KB Output is correct
13 Correct 51 ms 7888 KB Output is correct
14 Correct 53 ms 8256 KB Output is correct

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 26 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -