oj.uz

답안 #648798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648798 2022-10-08T10:35:26 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 = 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 = 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());
}

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();
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10132 KB Output is correct
2 Correct 6 ms 10064 KB Output is correct
3 Correct 8 ms 10064 KB Output is correct
4 Correct 11 ms 10244 KB Output is correct
5 Correct 13 ms 10604 KB Output is correct
6 Correct 29 ms 10960 KB Output is correct
7 Correct 35 ms 11600 KB Output is correct
8 Correct 44 ms 12240 KB Output is correct
9 Correct 85 ms 15636 KB Output is correct
10 Correct 159 ms 20952 KB Output is correct
11 Correct 245 ms 26352 KB Output is correct
12 Correct 342 ms 31912 KB Output is correct
13 Correct 403 ms 35656 KB Output is correct
14 Correct 531 ms 42484 KB Output is correct
15 Correct 834 ms 55608 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5207 ms 91848 KB Output is correct
2 Correct 6121 ms 95760 KB Output is correct
3 Execution timed out 8023 ms 109544 KB Time limit exceeded
4 Correct 863 ms 42436 KB Output is correct
5 Correct 1305 ms 51604 KB Output is correct
6 Correct 2626 ms 66248 KB Output is correct
7 Correct 5582 ms 85504 KB Output is correct
8 Correct 7634 ms 122632 KB Output is correct
9 Runtime error 242 ms 131072 KB Execution killed with signal 9
10 Runtime error 219 ms 131072 KB Execution killed with signal 9
11 Runtime error 239 ms 131072 KB Execution killed with signal 9
12 Runtime error 277 ms 131072 KB Execution killed with signal 9
13 Runtime error 235 ms 131072 KB Execution killed with signal 9
14 Runtime error 284 ms 131072 KB Execution killed with signal 9
15 Runtime error 213 ms 131072 KB Execution killed with signal 9
16 Runtime error 212 ms 131072 KB Execution killed with signal 9
17 Runtime error 256 ms 131072 KB Execution killed with signal 9