제출 #837272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837272		ymm	디지털 회로 (IOI22_circuit)	C++17	46 / 100	3095 ms	7888 KiB

circuit

#include "circuit.h"
#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;
using namespace std;

const int mod = 1'000'002'022;
const int N = 200'010;
vector<int> A[N];
ll kol[N];
ll val[N];

void dfskol(int v)
{
	if (A[v].empty()) {
		kol[v] = 1;
		return;
	}
	kol[v] = A[v].size();
	for (int u : A[v]) {
		dfskol(u);
		kol[v] = kol[v] * kol[u] % mod;
	}
}
void dfsval(int v, ll val)
{
	if (A[v].empty()) {
		::val[v] = val;
		return;
	}
	vector<ll> vec;
	for (int u : A[v])
		vec.push_back(kol[u]);
	vector<ll> pre = {1}, suf = {1};
	Loop (i,0,vec.size()-1)
		pre.push_back(pre.back() * vec[i] % mod);
	LoopR (i,1,vec.size())
		suf.push_back(suf.back() * vec[i] % mod);
	reverse(suf.begin(), suf.end());
	Loop (i,0,A[v].size())
		dfsval(A[v][i], val * pre[i] % mod * suf[i] % mod);
}

namespace seg {
	ll val[N];
	bool state[N];
	int st, fi;

	void init(int l, int r, ll *v, int *s) {
		st = l;
		fi = r;
		Loop (i,st,fi) {
			val[i] = v[i];
			state[i] = s[i];
		}
	}

	void up(int l, int r) {
		Loop (i,l,r)
			state[i] = !state[i];
	}
	ll get() {
		ll ans = 0;
		Loop (i,st,fi) {
			ans += state[i]? val[i]: 0;
			ans %= mod;
		}
		return ans;
	}
}
	

void init(int n, int m, std::vector<int> P, std::vector<int> A) {
	Loop (i,1,n+m)
		::A[P[i]].push_back(i);
	dfskol(0);
	dfsval(0, 1);
	seg::init(n, n+m, val, A.data() - n);
}

int count_ways(int L, int R) {
	seg::up(L, R+1);
	return seg::get();
}

• 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