oj.uz

Submission #648800

# Submission time Handle Problem Language Result Execution time Memory
648800 2022-10-08T10:37:37 Z ymm Regions (IOI09_regions) C++17
55 / 100
 5106 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];
unsigned char 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 6 ms 9900 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 10 ms 10064 KB Output is correct
5 Correct 13 ms 10344 KB Output is correct
6 Correct 21 ms 10704 KB Output is correct
7 Correct 30 ms 11344 KB Output is correct
8 Correct 36 ms 11856 KB Output is correct
9 Correct 55 ms 15056 KB Output is correct
10 Correct 116 ms 19916 KB Output is correct
11 Correct 143 ms 24912 KB Output is correct
12 Correct 194 ms 30044 KB Output is correct
13 Correct 178 ms 33480 KB Output is correct
14 Correct 286 ms 39764 KB Output is correct
15 Correct 436 ms 52296 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2432 ms 85668 KB Output is correct
2 Correct 2873 ms 89028 KB Output is correct
3 Correct 5106 ms 102064 KB Output is correct
4 Correct 482 ms 39840 KB Output is correct
5 Correct 666 ms 48452 KB Output is correct
6 Correct 1542 ms 61836 KB Output is correct
7 Correct 3176 ms 79816 KB Output is correct
8 Correct 4535 ms 114228 KB Output is correct
9 Runtime error 151 ms 131072 KB Execution killed with signal 9
10 Runtime error 147 ms 131072 KB Execution killed with signal 9
11 Runtime error 155 ms 131072 KB Execution killed with signal 9
12 Runtime error 170 ms 131072 KB Execution killed with signal 9
13 Runtime error 162 ms 131072 KB Execution killed with signal 9
14 Runtime error 162 ms 131072 KB Execution killed with signal 9
15 Runtime error 153 ms 131072 KB Execution killed with signal 9
16 Runtime error 143 ms 131072 KB Execution killed with signal 9
17 Runtime error 161 ms 131072 KB Execution killed with signal 9