Submission #648803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648803	2022-10-08T10:46:15 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 = 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];
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;
}
 
int compress(int i, int x)
{
	auto it = lower_bound(bl_regs[i].begin(), bl_regs[i].end(), x);
	if (it == bl_regs[i].end() || *it != x)
		return S;
	return it - bl_regs[i].begin();
}
 
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 = 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);
	static int arr[R];
	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())
		arr[bl_regs[bl][i]] = i;
	Loop (i,l,r)
		exp_reg[i] = arr[exp_reg[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][exp_reg[i]]++;
			scnt[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	9808 KB	Output is correct
2	Correct	6 ms	9872 KB	Output is correct
3	Correct	8 ms	9808 KB	Output is correct
4	Correct	11 ms	9936 KB	Output is correct
5	Correct	14 ms	10192 KB	Output is correct
6	Correct	26 ms	10288 KB	Output is correct
7	Correct	39 ms	10704 KB	Output is correct
8	Correct	53 ms	11088 KB	Output is correct
9	Correct	83 ms	13008 KB	Output is correct
10	Correct	169 ms	15696 KB	Output is correct
11	Correct	317 ms	18636 KB	Output is correct
12	Correct	455 ms	21700 KB	Output is correct
13	Correct	488 ms	23504 KB	Output is correct
14	Correct	614 ms	27208 KB	Output is correct
15	Correct	1074 ms	35656 KB	Output is correct

Subtask #2

20.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7289 ms	54292 KB	Output is correct
2	Execution timed out	8029 ms	55612 KB	Time limit exceeded
3	Execution timed out	8037 ms	64476 KB	Time limit exceeded
4	Correct	1096 ms	27188 KB	Output is correct
5	Correct	1765 ms	32928 KB	Output is correct
6	Correct	4576 ms	40192 KB	Output is correct
7	Execution timed out	8028 ms	50568 KB	Time limit exceeded
8	Execution timed out	8090 ms	72380 KB	Time limit exceeded
9	Execution timed out	8051 ms	98196 KB	Time limit exceeded
10	Execution timed out	8050 ms	114624 KB	Time limit exceeded
11	Execution timed out	8052 ms	124136 KB	Time limit exceeded
12	Execution timed out	8035 ms	120824 KB	Time limit exceeded
13	Execution timed out	8023 ms	121232 KB	Time limit exceeded
14	Execution timed out	8095 ms	126076 KB	Time limit exceeded
15	Execution timed out	8096 ms	130808 KB	Time limit exceeded
16	Runtime error	173 ms	131072 KB	Execution killed with signal 9
17	Runtime error	181 ms	131072 KB	Execution killed with signal 9