oj.uz

답안 #648786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648786 2022-10-08T10:11:00 Z ymm Regions (IOI09_regions) C++17
50 / 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 = 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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