oj.uz

답안 #648788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648788 2022-10-08T10:25:25 Z ymm Regions (IOI09_regions) C++17
1 / 100
 5938 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];
char compress[N/S][R];
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;
}

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());
	fill(compress[bl], compress[bl]+R, S);
	Loop (i,0,bl_regs[bl].size())
		compress[bl][bl_regs[bl][i]] = 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][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();
	}
}

Compilation message

regions.cpp: In function 'void init()':
regions.cpp:71:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   71 |     cnt[l/S][compress[l/S][exp_reg[i]]]++;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^
regions.cpp:72:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   72 |    scnt[l/S][compress[l/S][exp_reg[i]]] += delta[i];
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9936 KB Output is correct
2 Incorrect 5 ms 9936 KB Output isn't correct
3 Incorrect 6 ms 9936 KB Output isn't correct
4 Incorrect 10 ms 10064 KB Output isn't correct
5 Incorrect 13 ms 10320 KB Output isn't correct
6 Incorrect 25 ms 10576 KB Output isn't correct
7 Incorrect 35 ms 11344 KB Output isn't correct
8 Incorrect 44 ms 11856 KB Output isn't correct
9 Incorrect 48 ms 15000 KB Output isn't correct
10 Incorrect 89 ms 19536 KB Output isn't correct
11 Incorrect 149 ms 24400 KB Output isn't correct
12 Incorrect 192 ms 29312 KB Output isn't correct
13 Incorrect 239 ms 32720 KB Output isn't correct
14 Incorrect 264 ms 38728 KB Output isn't correct
15 Incorrect 502 ms 50840 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3230 ms 83052 KB Output isn't correct
2 Incorrect 3358 ms 86148 KB Output isn't correct
3 Incorrect 5938 ms 98916 KB Output isn't correct
4 Incorrect 477 ms 38692 KB Output isn't correct
5 Incorrect 681 ms 47176 KB Output isn't correct
6 Incorrect 1902 ms 59976 KB Output isn't correct
7 Incorrect 3951 ms 77256 KB Output isn't correct
8 Incorrect 5658 ms 110636 KB Output isn't correct
9 Runtime error 149 ms 131072 KB Execution killed with signal 9
10 Runtime error 156 ms 131072 KB Execution killed with signal 9
11 Runtime error 185 ms 131072 KB Execution killed with signal 9
12 Runtime error 177 ms 131072 KB Execution killed with signal 9
13 Runtime error 158 ms 131072 KB Execution killed with signal 9
14 Runtime error 169 ms 131072 KB Execution killed with signal 9
15 Runtime error 151 ms 131072 KB Execution killed with signal 9
16 Runtime error 163 ms 131072 KB Execution killed with signal 9
17 Runtime error 137 ms 131072 KB Execution killed with signal 9