Submission #1232585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232585		nicolo_010	Digital Circuit (IOI22_circuit)	C++20	0 / 100	187 ms	7824 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
const int MOD = 1000002022;

v<v<int>> adj;
v<v<int>> rev;
v<int> in;
v<int> pref;
int n;
int t;

void dfs1(int u, int p=-1) {
	in[u] = t;
	//cout << u << " " << t << endl;
	t--;
	for (auto x : rev[u]) {
		//cout << x << " ";
		if (x != p && x < n) {
			dfs1(x, u);
		}
	}
	//cout << endl;
}
v<int> s;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n = N;
	s = A;
	int NM = P.size();
	v<int> par(n, 0);
	adj.resize(NM);
	rev.resize(NM);
	rep(i, 1, NM) {
		par[P[i]]++;
	}
	//cout << N << endl;
	rep(i, 1, NM) {
		adj[i].push_back(P[i]);
		rev[P[i]].push_back(i);
	}
	in.resize(n);
	t = n-1;
	dfs1(0);
	v<int> a(n);
	rep(i, 0, n) {
		a[in[i]] = par[i];
		//cout << in[i] << " " << par[i] << " " << i << endl;
	}
	pref.resize(n);
	pref[0] = a[0];
	rep(i, 1, n) {
		pref[i] = pref[i-1] * a[i];
		pref[i] %= MOD;
	}
	//rep(i, 0, n) cout << pref[i] << " ";
}

ll backtrack(int u) {
	//cout << u << endl;
	int bl = 0;
	int p = -1;
	int cnt = 0;
	for (auto x : rev[u]) {
		if (x < n) p = x;
		else {
			bl += s[x-n];
			// cout << x << " " << s[x-n] << endl;
		}
	}
	//cout << u << " "<< p << " " << bl << endl;
	ll ans = 0;
	if (p==-1) {
		if (bl == 1) return 1;
		else if (bl == 2) return 2;
		else return 0;

	}
	if (bl == 1) {
		ans += pref[in[p]];
		ans %= MOD;
		ans += backtrack(p);
		ans %= MOD;
	}
	else {
		ans += backtrack(p);
		ans %= MOD;
	}
	return ans;
}

int count_ways(int L, int R) {
	L -= n, R -= n;
	int m = s.size();
	rep(i, L, R+1) {
		s[i] ^= 1;
		//cout << i << " " << s[i] << endl;
	}
	ll ans = backtrack(0);
	ans %= MOD;
	int ansi = ans;
	return ansi;
}

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