Submission #648785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648785	2022-10-08T10:06:42 Z	ymm	Regions (IOI09_regions)	C++17	35 / 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 = 512;
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];
int 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	4 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	7 ms	5072 KB	Output is correct
5	Correct	12 ms	5200 KB	Output is correct
6	Correct	115 ms	6504 KB	Output is correct
7	Correct	90 ms	6600 KB	Output is correct
8	Correct	180 ms	7712 KB	Output is correct
9	Correct	976 ms	15636 KB	Output is correct
10	Correct	1364 ms	21988 KB	Output is correct
11	Correct	1546 ms	28184 KB	Output is correct
12	Correct	5064 ms	52408 KB	Output is correct
13	Correct	2506 ms	42104 KB	Output is correct
14	Correct	2199 ms	43828 KB	Output is correct
15	Correct	5550 ms	78612 KB	Output is correct

Subtask #2

20.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5673 ms	96792 KB	Output is correct
2	Correct	4520 ms	83968 KB	Output is correct
3	Runtime error	7602 ms	131072 KB	Execution killed with signal 9
4	Correct	5245 ms	63996 KB	Output is correct
5	Execution timed out	8050 ms	66808 KB	Time limit exceeded
6	Correct	7593 ms	98032 KB	Output is correct
7	Execution timed out	8076 ms	91228 KB	Time limit exceeded
8	Execution timed out	8055 ms	85336 KB	Time limit exceeded
9	Execution timed out	8077 ms	73884 KB	Time limit exceeded
10	Execution timed out	8096 ms	84688 KB	Time limit exceeded
11	Execution timed out	8082 ms	106540 KB	Time limit exceeded
12	Execution timed out	8058 ms	107940 KB	Time limit exceeded
13	Execution timed out	8087 ms	92344 KB	Time limit exceeded
14	Execution timed out	8058 ms	113396 KB	Time limit exceeded
15	Execution timed out	8096 ms	86068 KB	Time limit exceeded
16	Execution timed out	8080 ms	92856 KB	Time limit exceeded
17	Execution timed out	8089 ms	97084 KB	Time limit exceeded