제출 #648776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648776		ymm	Regions (IOI09_regions)	C++17	30 / 100	8095 ms	25416 KiB

regions

#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'032;
int reg[N];
short exp_reg[2*N];
short delta[2*N];
int len = 0;
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;
}

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
int solve(short r1, short r2)
{
	typedef short ymm __attribute((vector_size(32)));
	int ans = 0, pre = 0;
	int len = ::len/16+1;
	Loop (i,0,len) {
		ymm r = ((ymm *)exp_reg)[i];
		ymm d = ((ymm *)delta)[i];
		d &= r == r1;
		r = r == r2;
		Loop (j,0,16) {
			ans += pre & r[j];
			pre += d[j];
		}
	}
	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);
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		cout << solve(r1, r2) << '\n';
		cout.flush();
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 85