oj.uz

Submission #837267

# Submission time Handle Problem Language Result Execution time Memory
837267 2023-08-25T08:53:54 Z ymm Digital Circuit (IOI22_circuit) C++17
2 / 100
 3000 ms 7836 KB 
#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;
		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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 7836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 7836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Incorrect 2 ms 4944 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -