Submission #787974

#	Time	Username	Problem	Language	Result	Execution time	Memory
787974		khshg	Digital Circuit (IOI22_circuit)	C++17	0 / 100	377 ms	4416 KiB

circuit

#include"circuit.h"
#include<bits/stdc++.h>
using namespace std;

const long long MOD =  1000002022;

long long MUL(long long A, long long B) {
	return A * B % MOD;
}

long long ADD(long long A, long long B) {
	A += B;
	if(A >= MOD) A -= MOD;
	return A;
}

long long SUB(long long A, long long B) {
	return ADD(A, MOD - B);
}

int N, M;
vector<vector<int>> ch;
vector<int> par, stat;
vector<long long> sz, val;
long long ans;

void dfs(int s) {
	if(ch[s].empty()) {
		sz[s] = 1LL;
		return;
	}
	sz[s] = 2LL;
	for(auto& u : ch[s]) {
		dfs(u);
		sz[s] = MUL(sz[s], sz[u]);
	}
}

void ass_val(int s, long long v) {
	if(ch[s].empty()) { val[s - N] = v; return; }
	ass_val(ch[s][0], MUL(v, sz[ch[s][1]]));
	ass_val(ch[s][1], MUL(v, sz[ch[s][0]]));
}

void init(int _N, int _M, vector<int> P, vector<int> A) {
	N = _N; M = _M;
	swap(P, par);
	swap(A, stat);
	val.resize(M);
	ch.resize(N + M);
	sz.resize(N + M);
	for(int i = 1; i < N + M; ++i) {
		ch[par[i]].push_back(i);
	}
	dfs(0);
	ass_val(0, 1LL);
	for(int i = 0; i < M; ++i) {
		if(stat[i]) ans = ADD(ans, val[i]);
	}
}

int count_ways(int L, int R) {
	L -= N;
	if(stat[L]) ans = SUB(ans, val[L]);
	stat[L] = stat[L] ^ true;
	return ans;
}

• 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