oj.uz

Submission #648792

# Submission time Handle Problem Language Result Execution time Memory
648792 2022-10-08T10:29:56 Z ymm Regions (IOI09_regions) C++17
45 / 100
 3830 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 = 150;
const int N = 400'032 + S;
const int R = 25'010;
int reg[N];
int len = 0;
int exp_reg[N];
int delta[N];
short compress[N/S][R];
vector<int> bl_regs[N/S];
int cnt[N/S][S+1];
int scnt[N/S][S+1];
short 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 5 ms 9936 KB Output is correct
2 Correct 5 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 11 ms 10064 KB Output is correct
5 Correct 14 ms 10576 KB Output is correct
6 Correct 23 ms 10960 KB Output is correct
7 Correct 40 ms 11856 KB Output is correct
8 Correct 41 ms 12560 KB Output is correct
9 Correct 56 ms 16720 KB Output is correct
10 Correct 97 ms 23120 KB Output is correct
11 Correct 117 ms 29812 KB Output is correct
12 Correct 173 ms 36648 KB Output is correct
13 Correct 208 ms 41288 KB Output is correct
14 Correct 282 ms 49480 KB Output is correct
15 Correct 395 ms 65420 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2666 ms 110152 KB Output is correct
2 Correct 2934 ms 115144 KB Output is correct
3 Runtime error 119 ms 131072 KB Execution killed with signal 9
4 Correct 467 ms 49504 KB Output is correct
5 Correct 986 ms 60472 KB Output is correct
6 Correct 2071 ms 78884 KB Output is correct
7 Correct 3830 ms 102600 KB Output is correct
8 Runtime error 138 ms 131072 KB Execution killed with signal 9
9 Runtime error 148 ms 131072 KB Execution killed with signal 9
10 Runtime error 165 ms 131072 KB Execution killed with signal 9
11 Runtime error 156 ms 131072 KB Execution killed with signal 9
12 Runtime error 159 ms 131072 KB Execution killed with signal 9
13 Runtime error 148 ms 131072 KB Execution killed with signal 9
14 Runtime error 167 ms 131072 KB Execution killed with signal 9
15 Runtime error 144 ms 131072 KB Execution killed with signal 9
16 Runtime error 139 ms 131072 KB Execution killed with signal 9
17 Runtime error 138 ms 131072 KB Execution killed with signal 9