Submission #681570

#	Time	Username	Problem	Language	Result	Execution time	Memory
681570		Justin1	Digital Circuit (IOI22_circuit)	C++17	46 / 100	3049 ms	8348 KiB

circuit

//0 - n-1 = non leaf, n - m-1 = leaf
 
#include "circuit.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int mod = 1e9 + 2022;
int n, m, k, x, y, z;
int val[200005], cont[200005], cur[200005];
vector<signed> par, gph[200005];

void dfs(int id) {
	val[id] = id >= n ? 1 : gph[id].size();
	for (auto i : gph[id]) dfs(i), val[id] = val[id] * val[i] % mod;
}

void dfs2(int id, int cur) {
	cont[id] = cur;
	int post[gph[id].size()+2], pre = 1;
	post[gph[id].size()+1] = 1;
	for (int i = gph[id].size(); i >= 1; i--) post[i] = post[i+1] * val[gph[id][i-1]] % mod;
	for (int i = 1; i <= gph[id].size(); i++) {
		dfs2(gph[id][i-1], cur * pre % mod * post[i+1] % mod);
		pre = pre * val[gph[id][i-1]] % mod;
	}
}
 
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N, m = M, par = P;
	for (int i = 1; i < n + m; i++) gph[P[i]].push_back(i);
	for (int i = n; i < n + m; i++) cur[i] = A[i-n];
	dfs(0);
	dfs2(0, 1);
}

signed count_ways(signed L, signed R) {
	int ans = 0;
	for (int i = L; i <= R; i++) cur[i] ^= 1;
	for (int i = n; i < n + m; i++) {
		ans += cont[i] * cur[i];
		ans %= mod;
	}
	return ans;
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(long long int, long long int)':
circuit.cpp:23:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 1; i <= gph[id].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 28 / 28
• Subtask 8: 0 / 11