oj.uz

답안 #648803

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

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

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