oj.uz

Submission #648791

# Submission time Handle Problem Language Result Execution time Memory
648791 2022-10-08T10:27:30 Z ymm Regions (IOI09_regions) C++17
25 / 100
 1145 ms 131072 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int S = 128;
const int N = 400'032 + S;
const int R = 25'010;
int reg[N];
int len = 0;
int exp_reg[N];
int delta[N];
int compress[N/S][R];
vector<int> bl_regs[N/S];
int cnt[N/S][S+1];
int scnt[N/S][S+1];
int sum[N/S][S+1][S+1];
vector<int> A[N];
int n, r, q;

void dfs(int v)
{
	exp_reg[len] = reg[v];
	delta[len] = 1;
	++len;
	for (int u : A[v])
		dfs(u);
	exp_reg[len] = reg[v];
	delta[len] = -1;
	++len;
}

void calc_block(int bl)
{
	int l = bl*S, r = min(bl*S+S, len);
	int ans[S][S] = {}, pre[S] = {};
	Loop (i,l,r) {
		int reg = compress[bl][exp_reg[i]];
		Loop (j,0,S)
			ans[reg][j] += pre[j];
		pre[reg] += delta[i];
	}
	Loop (i,0,S) Loop (j,0,S)
		sum[bl][i][j] = ans[j][i];
}

void comp_block(int bl)
{
	int l = bl*S, r = min(bl*S+S, len);
	Loop (i,l,r)
		bl_regs[bl].push_back(exp_reg[i]);
	sort(bl_regs[bl].begin(), bl_regs[bl].end());
	bl_regs[bl].resize(  unique(bl_regs[bl].begin(), bl_regs[bl].end())
	                   - bl_regs[bl].begin());
	fill(compress[bl], compress[bl]+R, S);
	Loop (i,0,bl_regs[bl].size())
		compress[bl][bl_regs[bl][i]] = i;
}

void init()
{
	for (int l = 0; l < len; l += S)
	{
		int r = min(len, l + S);
		comp_block(l/S);
		calc_block(l/S);
		Loop (i,l,r) {
			 cnt[l/S][compress[l/S][exp_reg[i]]]++;
			scnt[l/S][compress[l/S][exp_reg[i]]] += delta[i];
		}
	}
}

int solve(int r1, int r2)
{
	int ans = 0, pre = 0;
	Loop (i,0,(len+S-1)/S) {
		int cr1 = compress[i][r1];
		int cr2 = compress[i][r2];
		ans += pre * cnt[i][cr2];
		ans += sum[i][cr1][cr2];
		pre += scnt[i][cr1];
	}
	return ans/2;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> r >> q;
	cin >> reg[0];
	Loop (i,1,n) {
		int p;
		cin >> p >> reg[i];
		A[p-1].push_back(i);
	}
	dfs(0);
	init();
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		cout << solve(r1, r2) << '\n';
		cout.flush();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10064 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 7 ms 10064 KB Output is correct
4 Correct 10 ms 10340 KB Output is correct
5 Correct 13 ms 11216 KB Output is correct
6 Correct 23 ms 11984 KB Output is correct
7 Correct 23 ms 13904 KB Output is correct
8 Correct 34 ms 15252 KB Output is correct
9 Correct 61 ms 23376 KB Output is correct
10 Correct 116 ms 36188 KB Output is correct
11 Correct 149 ms 49224 KB Output is correct
12 Correct 239 ms 62700 KB Output is correct
13 Correct 264 ms 72420 KB Output is correct
14 Correct 362 ms 88392 KB Output is correct
15 Correct 565 ms 117124 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 131072 KB Execution killed with signal 9
2 Runtime error 101 ms 131072 KB Execution killed with signal 9
3 Runtime error 94 ms 131072 KB Execution killed with signal 9
4 Correct 530 ms 88412 KB Output is correct
5 Correct 1145 ms 108540 KB Output is correct
6 Runtime error 91 ms 131072 KB Execution killed with signal 9
7 Runtime error 117 ms 131072 KB Execution killed with signal 9
8 Runtime error 99 ms 131072 KB Execution killed with signal 9
9 Runtime error 129 ms 131072 KB Execution killed with signal 9
10 Runtime error 124 ms 131072 KB Execution killed with signal 9
11 Runtime error 127 ms 131072 KB Execution killed with signal 9
12 Runtime error 156 ms 131072 KB Execution killed with signal 9
13 Runtime error 142 ms 131072 KB Execution killed with signal 9
14 Runtime error 125 ms 131072 KB Execution killed with signal 9
15 Runtime error 125 ms 131072 KB Execution killed with signal 9
16 Runtime error 129 ms 131072 KB Execution killed with signal 9
17 Runtime error 113 ms 131072 KB Execution killed with signal 9