oj.uz

답안 #1063645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063645 2024-08-17T22:05:17 Z Arapak 디지털 회로 (IOI22_circuit) C++17
2 / 100
 3000 ms 4184 KB 
#include "circuit.h"
#include "bits/stdc++.h"

using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

const ll mod = 1000002022;

// struct SegTree {

// }

int n, m;
vi p, a;
vector<vi> g;

vector<ll> mult;
void dfs_mult(int v) {
	if(v >= n) return;
	dbg(v, g[v]);
	mult[v] = ll(sz(g[v]));
	for(auto e : g[v]) {
		dfs_mult(e);
		if(e < n)
			mult[v] = mult[v] * mult[e] % mod;
	}
}

vector<ll> weight;
void dfs(int v, ll w) {
	if(v >= n) {
		weight[v - n] = w;
		return;
	}
	dbg(v, w);
	vector<ll> pref(sz(g[v]) + 1, 1), suff(sz(g[v]) + 1, 1);
	rep(i,0,sz(g[v])) {
		pref[i+1] = (pref[i] * mult[g[v][i]]) % mod;
		suff[i+1] = (suff[i] * mult[g[v][sz(g[v]) -i-1]]) % mod;
	}
	dbg(pref, suff);

	rep(i,0,sz(g[v])) {
		ll we = pref[i] * suff[i] % mod;
		dfs(g[v][i], w * we % mod);
	}
	
}

void init(int N, int M, vi P, vi A) {
	n = N; m = M; p = P; a = A;
	g.resize(n);
	rep(i,1,n+m)
		g[p[i]].push_back(i);
	mult.assign(n+m, 1);
	dfs_mult(0);
	dbg(mult);
	weight.resize(m);
	dfs(0, 1);
	dbg(weight);
}

int count_ways(int L, int R) {
	rep(i,L-n,R-n+1)
		a[i] = !a[i];

	ll res = 0;
	rep(i,0,m)
		if(a[i]) res = (res + weight[i]) % mod;

	return (int)res;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '537994245'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '537994245'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3005 ms 4184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3005 ms 4184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '537994245'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '537994245'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '537994245'
11 Halted 0 ms 0 KB -