제출 #645286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645286		dozer	디지털 회로 (IOI22_circuit)	C++17	50 / 100	1362 ms	2097152 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define L(node) node * 2
#define R(node) node * 2 + 1
#define ll long long

const int modulo = 1000002022;

vector<int> adj[2000005];
int sz[400005], arr[400005], tree[2000005 * 4], tree2[2000005 * 4], lazy[2000005 * 4];
int n, m;


ll add(ll a, ll b)
{
	return (a + b) % modulo;
}

ll subs(ll a, ll b)
{
	return (((a - b) % modulo) + modulo) % modulo;
}

ll mul(ll a, ll b)
{
	return (a * b) % modulo;
}

int dfs(int node, int root)
{
	if (adj[node].empty()) return sz[node] = 1;
	sz[node] = 2;
	for (auto i : adj[node])
		sz[node] = mul(sz[node], dfs(i, node));
	return sz[node];
}

void dfs2(int node, int root, int val)
{
	arr[node] = val;
	if (adj[node].empty())
	{
		return;
	}
	dfs2(adj[node][1], node, mul(val, sz[adj[node][0]]));
	dfs2(adj[node][0], node, mul(val, sz[adj[node][1]]));
}	

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = arr[l - 1];
		return;
	}
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
	tree[node] = add(tree[L(node)], tree[R(node)]);
}


void push(int node, int l, int r)
{
	if (lazy[node] == 0) return;
	tree2[node] = subs(tree[node], tree2[node]);
	lazy[node] = 0;
	if (l == r)
		return;
	lazy[L(node)] ^= 1;
	lazy[R(node)] ^= 1;
}

void update(int node, int l, int r, int sl, int sr)
{
	push(node, l, r);
	if (l > r || l > sr || r < sl) return;
	int mid = (l + r) / 2;
	if (l >= sl && r <= sr)
	{
		lazy[node] ^= 1;
		push(node, l, r);
		return;
	}
	push(node, l, r);
	update(L(node), l, mid, sl, sr);
	update(R(node), mid + 1, r, sl, sr);
	tree2[node] = add(tree2[L(node)], tree2[R(node)]);
}

int sum(int node, int l, int r, int sl, int sr)
{
	push(node, l, r);
	if (l > r || l > sr || r < sl) return 0;
	if (l >= sl && r <= sr) return tree2[node];
	int mid = (l + r) / 2;
	return add(sum(L(node), l, mid, sl, sr), sum(R(node), mid + 1, r, sl, sr));
}


void init(int N, int M, vector<int> P, vector<int> A)
{
	n = N, m = M;
	for (int i = 1; i < N + M; i++)
		adj[P[i]].pb(i);
	int tmp = dfs(0, -1);
	dfs2(0, -1, 1);
	build(1, 1, N + M);
	for (int i = 0; i < M; i++)
		if (A[i]) update(1, 1, N + M, N + i + 1, N + i + 1);
}

int count_ways(int L, int R)
{
	update(1, 1, n + m, L + 1, R + 1);
	return sum(1, 1, n + m, 1, n + m);
}

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:112:6: warning: unused variable 'tmp' [-Wunused-variable]
  112 |  int tmp = dfs(0, -1);
      |      ^~~

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