oj.uz

Submission #648776

# Submission time Handle Problem Language Result Execution time Memory
648776 2022-10-08T09:13:47 Z ymm Regions (IOI09_regions) C++17
30 / 100
 8000 ms 25416 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'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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 5 ms 5072 KB Output is correct
4 Correct 7 ms 4944 KB Output is correct
5 Correct 11 ms 4944 KB Output is correct
6 Correct 25 ms 5072 KB Output is correct
7 Correct 42 ms 5072 KB Output is correct
8 Correct 51 ms 5072 KB Output is correct
9 Correct 96 ms 5456 KB Output is correct
10 Correct 276 ms 5428 KB Output is correct
11 Correct 450 ms 5584 KB Output is correct
12 Correct 567 ms 6076 KB Output is correct
13 Correct 880 ms 5584 KB Output is correct
14 Correct 1137 ms 6116 KB Output is correct
15 Correct 1695 ms 9240 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8060 ms 9040 KB Time limit exceeded
2 Execution timed out 8038 ms 7632 KB Time limit exceeded
3 Execution timed out 8016 ms 11028 KB Time limit exceeded
4 Correct 1986 ms 6096 KB Output is correct
5 Correct 2922 ms 8144 KB Output is correct
6 Correct 6476 ms 7240 KB Output is correct
7 Execution timed out 8086 ms 7880 KB Time limit exceeded
8 Execution timed out 8036 ms 13508 KB Time limit exceeded
9 Execution timed out 8019 ms 12228 KB Time limit exceeded
10 Execution timed out 8029 ms 17844 KB Time limit exceeded
11 Execution timed out 8048 ms 11080 KB Time limit exceeded
12 Execution timed out 8045 ms 13252 KB Time limit exceeded
13 Execution timed out 8095 ms 13732 KB Time limit exceeded
14 Execution timed out 8060 ms 12904 KB Time limit exceeded
15 Execution timed out 8029 ms 17908 KB Time limit exceeded
16 Execution timed out 8037 ms 25416 KB Time limit exceeded
17 Execution timed out 8070 ms 23884 KB Time limit exceeded