oj.uz

Submission #648824

# Submission time Handle Problem Language Result Execution time Memory
648824 2022-10-08T11:55:35 Z ymm Regions (IOI09_regions) C++17
1 / 100
 872 ms 64880 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 N = 200'064;
int rg[N];
short reg[2*N];
char delta[2*N];
int len = 0, len31;
vector<int> A[N];
int n, r, q;
char sum[2*N/32][32][32];
char cnt[2*N/32][32];
char scnt[2*N/32][32];

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,abm,bmi,bmi2")
typedef char  c32 __attribute__((vector_size(32)));
typedef short s16 __attribute__((vector_size(32)));

void dfs(int v)
{
	reg[len] = rg[v];
	delta[len] = 1;
	++len;
	for (int u : A[v])
		dfs(u);
	reg[len] = rg[v];
	delta[len] = -1;
	++len;
}

void init()
{
	len31 = len/31+1;
	Loop (i,0,len31)
	{
		int ii = i*31;
		Loop (ir1,0,31) {
			short r1 = reg[ii + ir1];
			Loop (j,ii,ii+31) {
				cnt[i][ir1] += reg[j] == r1;
				scnt[i][ir1] += delta[j] & -(reg[j] == r1);
			}
			Loop (ir2,0,31) {
				short r2 = reg[ii + ir2];
				char ans = 0, pre = 0;
				Loop (j,ii,ii+31) {
					ans += pre & -(reg[j] == r2);
					pre += delta[j] & -(reg[j] == r1);
				}
				sum[i][ir1][ir2] = ans;
			}
		}
	}
}

int solve(short r1, short r2)
{
	int ans = 0, pre = 0;
	for (int i = 0, ii = 0; i < len31; ++i, ii += 31) {
		s16 rl = *(s16 *)(reg+ii);
		s16 rr = *(s16 *)(reg+ii+16);
		c32 is_r1 = __builtin_ia32_packsswb256(rl == r1, rr == r1);
		c32 is_r2 = __builtin_ia32_packsswb256(rl == r2, rr == r2);
		int r1msk = __builtin_ia32_pmovmskb256(is_r1) | INT_MIN;
		int r2msk = __builtin_ia32_pmovmskb256(is_r2) | INT_MIN;
		int fr1 = __builtin_ctz(r1msk);
		int fr2 = __builtin_ctz(r2msk);
		ans += pre * cnt[i][fr2];
		ans += sum[i][fr1][fr2];
		pre += scnt[i][fr1];
	}
	return ans/2;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> r >> q;
	cin >> rg[0];
	Loop (i,1,n) {
		int p;
		cin >> p >> rg[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
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 8 ms 10064 KB Execution killed with signal 11
3 Runtime error 7 ms 10052 KB Execution killed with signal 11
4 Runtime error 9 ms 10044 KB Execution killed with signal 11
5 Runtime error 11 ms 10140 KB Execution killed with signal 11
6 Runtime error 11 ms 10192 KB Execution killed with signal 11
7 Runtime error 14 ms 10320 KB Execution killed with signal 11
8 Runtime error 16 ms 10448 KB Execution killed with signal 11
9 Runtime error 30 ms 11400 KB Execution killed with signal 11
10 Runtime error 54 ms 12160 KB Execution killed with signal 11
11 Runtime error 85 ms 13304 KB Execution killed with signal 11
12 Runtime error 99 ms 14724 KB Execution killed with signal 11
13 Runtime error 114 ms 14732 KB Execution killed with signal 11
14 Runtime error 136 ms 16372 KB Execution killed with signal 11
15 Runtime error 181 ms 21272 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 328 ms 27396 KB Execution killed with signal 11
2 Runtime error 350 ms 26056 KB Execution killed with signal 11
3 Runtime error 389 ms 32080 KB Execution killed with signal 11
4 Runtime error 134 ms 16372 KB Execution killed with signal 11
5 Runtime error 165 ms 19676 KB Execution killed with signal 11
6 Runtime error 235 ms 21252 KB Execution killed with signal 11
7 Runtime error 297 ms 25056 KB Execution killed with signal 11
8 Runtime error 437 ms 36364 KB Execution killed with signal 11
9 Runtime error 639 ms 43768 KB Execution killed with signal 11
10 Runtime error 728 ms 53044 KB Execution killed with signal 11
11 Runtime error 842 ms 48328 KB Execution killed with signal 11
12 Runtime error 830 ms 52348 KB Execution killed with signal 11
13 Runtime error 834 ms 52184 KB Execution killed with signal 11
14 Runtime error 865 ms 51860 KB Execution killed with signal 11
15 Runtime error 862 ms 57620 KB Execution killed with signal 11
16 Runtime error 872 ms 64880 KB Execution killed with signal 11
17 Runtime error 851 ms 63552 KB Execution killed with signal 11