oj.uz

답안 #648785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648785 2022-10-08T10:06:42 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 = 512;
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];
int 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 4 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 7 ms 5072 KB Output is correct
5 Correct 12 ms 5200 KB Output is correct
6 Correct 115 ms 6504 KB Output is correct
7 Correct 90 ms 6600 KB Output is correct
8 Correct 180 ms 7712 KB Output is correct
9 Correct 976 ms 15636 KB Output is correct
10 Correct 1364 ms 21988 KB Output is correct
11 Correct 1546 ms 28184 KB Output is correct
12 Correct 5064 ms 52408 KB Output is correct
13 Correct 2506 ms 42104 KB Output is correct
14 Correct 2199 ms 43828 KB Output is correct
15 Correct 5550 ms 78612 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5673 ms 96792 KB Output is correct
2 Correct 4520 ms 83968 KB Output is correct
3 Runtime error 7602 ms 131072 KB Execution killed with signal 9
4 Correct 5245 ms 63996 KB Output is correct
5 Execution timed out 8050 ms 66808 KB Time limit exceeded
6 Correct 7593 ms 98032 KB Output is correct
7 Execution timed out 8076 ms 91228 KB Time limit exceeded
8 Execution timed out 8055 ms 85336 KB Time limit exceeded
9 Execution timed out 8077 ms 73884 KB Time limit exceeded
10 Execution timed out 8096 ms 84688 KB Time limit exceeded
11 Execution timed out 8082 ms 106540 KB Time limit exceeded
12 Execution timed out 8058 ms 107940 KB Time limit exceeded
13 Execution timed out 8087 ms 92344 KB Time limit exceeded
14 Execution timed out 8058 ms 113396 KB Time limit exceeded
15 Execution timed out 8096 ms 86068 KB Time limit exceeded
16 Execution timed out 8080 ms 92856 KB Time limit exceeded
17 Execution timed out 8089 ms 97084 KB Time limit exceeded