oj.uz

Submission #648804

# Submission time Handle Problem Language Result Execution time Memory
648804 2022-10-08T10:46:52 Z ymm Regions (IOI09_regions) C++17
40 / 100
 8000 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 = 192;
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 7 ms 9936 KB Output is correct
2 Correct 6 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 7 ms 10064 KB Output is correct
5 Correct 13 ms 10320 KB Output is correct
6 Correct 30 ms 10576 KB Output is correct
7 Correct 43 ms 11216 KB Output is correct
8 Correct 56 ms 11600 KB Output is correct
9 Correct 74 ms 14288 KB Output is correct
10 Correct 168 ms 18288 KB Output is correct
11 Correct 295 ms 22456 KB Output is correct
12 Correct 394 ms 26796 KB Output is correct
13 Correct 399 ms 29604 KB Output is correct
14 Correct 752 ms 34992 KB Output is correct
15 Correct 949 ms 45680 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6672 ms 73292 KB Output is correct
2 Execution timed out 8051 ms 75912 KB Time limit exceeded
3 Execution timed out 8025 ms 87176 KB Time limit exceeded
4 Correct 935 ms 34840 KB Output is correct
5 Correct 1738 ms 42304 KB Output is correct
6 Correct 3507 ms 53340 KB Output is correct
7 Correct 7202 ms 68264 KB Output is correct
8 Execution timed out 8044 ms 97740 KB Time limit exceeded
9 Runtime error 185 ms 131072 KB Execution killed with signal 9
10 Runtime error 196 ms 131072 KB Execution killed with signal 9
11 Runtime error 205 ms 131072 KB Execution killed with signal 9
12 Runtime error 210 ms 131072 KB Execution killed with signal 9
13 Runtime error 189 ms 131072 KB Execution killed with signal 9
14 Runtime error 226 ms 131072 KB Execution killed with signal 9
15 Runtime error 208 ms 131072 KB Execution killed with signal 9
16 Runtime error 189 ms 131072 KB Execution killed with signal 9
17 Runtime error 183 ms 131072 KB Execution killed with signal 9