Submission #648786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648786	2022-10-08T10:11:00 Z	ymm	Regions (IOI09_regions)	C++17	50 / 100	8000 ms	131072 KB

regions

#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 = 256;
const int N = 200'032 + S;
const int R = 25'010;
int reg[N];
int len = 0;
int exp_reg[2*N];
int delta[2*N];
short compress[N/S][R];
vector<int> bl_regs[N/S];
int cnt[N/S][S];
int scnt[N/S][S];
short sum[N/S][S][S];
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 r1, int r2)
{
	int l = bl*S, r = min(bl*S+S, len);
	int ans = 0, pre = 0;
	Loop (i,l,r) {
		ans += pre & -(exp_reg[i] == r2);
		pre += delta[i] & -(exp_reg[i] == r1);
	}
	r1 = compress[bl][r1];
	r2 = compress[bl][r2];
	sum[bl][r1][r2] = ans;
}

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());
	Loop (i,0,bl_regs[bl].size())
		compress[bl][bl_regs[bl][i]] = i+1;
}

void init()
{
	for (int l = 0; l < len; l += S)
	{
		int r = min(len, l + S);
		comp_block(l/S);
		for (int r1 : bl_regs[l/S])
			for (int r2 : bl_regs[l/S])
				calc_block(l/S, r1, r2);
		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	3 ms	5072 KB	Output is correct
2	Correct	3 ms	5072 KB	Output is correct
3	Correct	5 ms	5072 KB	Output is correct
4	Correct	6 ms	5072 KB	Output is correct
5	Correct	11 ms	5200 KB	Output is correct
6	Correct	74 ms	5676 KB	Output is correct
7	Correct	67 ms	5788 KB	Output is correct
8	Correct	96 ms	6084 KB	Output is correct
9	Correct	466 ms	9416 KB	Output is correct
10	Correct	497 ms	11104 KB	Output is correct
11	Correct	757 ms	14280 KB	Output is correct
12	Correct	2192 ms	22604 KB	Output is correct
13	Correct	1058 ms	18136 KB	Output is correct
14	Correct	1139 ms	20632 KB	Output is correct
15	Correct	3228 ms	37336 KB	Output is correct

Subtask #2

35.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3813 ms	43168 KB	Output is correct
2	Correct	3284 ms	37224 KB	Output is correct
3	Correct	7037 ms	59020 KB	Output is correct
4	Correct	2059 ms	26864 KB	Output is correct
5	Correct	5536 ms	45096 KB	Output is correct
6	Correct	3534 ms	42520 KB	Output is correct
7	Correct	7391 ms	67432 KB	Output is correct
8	Execution timed out	8058 ms	88124 KB	Time limit exceeded
9	Execution timed out	8053 ms	88120 KB	Time limit exceeded
10	Execution timed out	8058 ms	96780 KB	Time limit exceeded
11	Runtime error	6507 ms	131072 KB	Execution killed with signal 6
12	Runtime error	7238 ms	131072 KB	Execution killed with signal 11
13	Runtime error	7723 ms	131072 KB	Execution killed with signal 6
14	Runtime error	5725 ms	131072 KB	Execution killed with signal 11
15	Execution timed out	8087 ms	109840 KB	Time limit exceeded
16	Execution timed out	8084 ms	110908 KB	Time limit exceeded
17	Execution timed out	8085 ms	114976 KB	Time limit exceeded