Submission #837275

#	Time	Username	Problem	Language	Result	Execution time	Memory
837275		ymm	Digital Circuit (IOI22_circuit)	C++17	100 / 100	904 ms	47656 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 {
	struct node {
		ll sum, sumr;
		bool swp;
	} t[4*N];
	int st, fi;

	void tag(int i) {
		swap(t[i].sum, t[i].sumr);
		t[i].swp ^= 1;
	}
	void ppg(int i) {
		if (t[i].swp) {
			tag(2*i+1);
			tag(2*i+2);
			t[i].swp = 0;
		}
	}
	void merge(int i) {
		t[i].sum = (t[2*i+1].sum + t[2*i+2].sum) % mod;
		t[i].sumr = (t[2*i+1].sumr + t[2*i+2].sumr) % mod;
	}

	void up(int l, int r, int i, int b, int e) {
		if (l <= b && e <= r)
			return tag(i);
		if (r <= b || e <= l)
			return;
		ppg(i);
		up(l, r, 2*i+1, b, (b+e)/2);
		up(l, r, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void up(int l, int r) { up(l, r, 0, st, fi); }

	void init(ll *v, int *s, int i, int b, int e) {
		if (e-b == 1) {
			t[i].sum = 0;
			t[i].sumr = v[b];
			if (s[b])
				swap(t[i].sum, t[i].sumr);
			return;
		}
		init(v, s, 2*i+1, b, (b+e)/2);
		init(v, s, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void init(int l, int r, ll *v, int *s) {
		st = l;
		fi = r;
		init(v, s, 0, st, fi);
	}

	ll get() { return t[0].sum; }
}
	

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: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11