Submission #648775

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648775	2022-10-08T09:06:30 Z	ymm	Regions (IOI09_regions)	C++17	25 / 100	8000 ms	24988 KB

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];
char 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(int r1, int r2)
{
	int ans = 0, pre = 0;
	Loop (i,0,len) {
		ans += pre & -(exp_reg[i] == r2);
		pre += delta[i] & -(exp_reg[i] == r1);
	}
	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	6 ms	4944 KB	Output is correct
4	Correct	7 ms	4944 KB	Output is correct
5	Correct	14 ms	4944 KB	Output is correct
6	Correct	24 ms	5072 KB	Output is correct
7	Correct	39 ms	5072 KB	Output is correct
8	Correct	61 ms	5072 KB	Output is correct
9	Correct	139 ms	5456 KB	Output is correct
10	Correct	363 ms	5328 KB	Output is correct
11	Correct	573 ms	5584 KB	Output is correct
12	Correct	894 ms	6096 KB	Output is correct
13	Correct	1186 ms	5700 KB	Output is correct
14	Correct	1508 ms	6096 KB	Output is correct
15	Correct	2438 ms	9116 KB	Output is correct

Subtask #2

10.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8047 ms	8840 KB	Time limit exceeded
2	Execution timed out	8061 ms	7352 KB	Time limit exceeded
3	Execution timed out	8007 ms	10824 KB	Time limit exceeded
4	Correct	2802 ms	6096 KB	Output is correct
5	Correct	4428 ms	8092 KB	Output is correct
6	Execution timed out	8085 ms	7120 KB	Time limit exceeded
7	Execution timed out	8036 ms	7752 KB	Time limit exceeded
8	Execution timed out	8004 ms	13256 KB	Time limit exceeded
9	Execution timed out	8061 ms	11848 KB	Time limit exceeded
10	Execution timed out	8021 ms	17412 KB	Time limit exceeded
11	Execution timed out	8013 ms	10660 KB	Time limit exceeded
12	Execution timed out	8032 ms	12888 KB	Time limit exceeded
13	Execution timed out	8019 ms	13300 KB	Time limit exceeded
14	Execution timed out	8007 ms	12472 KB	Time limit exceeded
15	Execution timed out	8071 ms	17632 KB	Time limit exceeded
16	Execution timed out	8095 ms	24988 KB	Time limit exceeded
17	Execution timed out	8090 ms	23496 KB	Time limit exceeded