Submission #648788

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648788	2022-10-08T10:25:25 Z	ymm	Regions (IOI09_regions)	C++17	1 / 100	5938 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];
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();
	}
}

Compilation message

regions.cpp: In function 'void init()':
regions.cpp:71:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   71 |     cnt[l/S][compress[l/S][exp_reg[i]]]++;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^
regions.cpp:72:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   72 |    scnt[l/S][compress[l/S][exp_reg[i]]] += delta[i];
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^

Subtask #1

1.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9936 KB	Output is correct
2	Incorrect	5 ms	9936 KB	Output isn't correct
3	Incorrect	6 ms	9936 KB	Output isn't correct
4	Incorrect	10 ms	10064 KB	Output isn't correct
5	Incorrect	13 ms	10320 KB	Output isn't correct
6	Incorrect	25 ms	10576 KB	Output isn't correct
7	Incorrect	35 ms	11344 KB	Output isn't correct
8	Incorrect	44 ms	11856 KB	Output isn't correct
9	Incorrect	48 ms	15000 KB	Output isn't correct
10	Incorrect	89 ms	19536 KB	Output isn't correct
11	Incorrect	149 ms	24400 KB	Output isn't correct
12	Incorrect	192 ms	29312 KB	Output isn't correct
13	Incorrect	239 ms	32720 KB	Output isn't correct
14	Incorrect	264 ms	38728 KB	Output isn't correct
15	Incorrect	502 ms	50840 KB	Output isn't correct

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3230 ms	83052 KB	Output isn't correct
2	Incorrect	3358 ms	86148 KB	Output isn't correct
3	Incorrect	5938 ms	98916 KB	Output isn't correct
4	Incorrect	477 ms	38692 KB	Output isn't correct
5	Incorrect	681 ms	47176 KB	Output isn't correct
6	Incorrect	1902 ms	59976 KB	Output isn't correct
7	Incorrect	3951 ms	77256 KB	Output isn't correct
8	Incorrect	5658 ms	110636 KB	Output isn't correct
9	Runtime error	149 ms	131072 KB	Execution killed with signal 9
10	Runtime error	156 ms	131072 KB	Execution killed with signal 9
11	Runtime error	185 ms	131072 KB	Execution killed with signal 9
12	Runtime error	177 ms	131072 KB	Execution killed with signal 9
13	Runtime error	158 ms	131072 KB	Execution killed with signal 9
14	Runtime error	169 ms	131072 KB	Execution killed with signal 9
15	Runtime error	151 ms	131072 KB	Execution killed with signal 9
16	Runtime error	163 ms	131072 KB	Execution killed with signal 9
17	Runtime error	137 ms	131072 KB	Execution killed with signal 9