oj.uz

Submission #1078038

# Submission time Handle Problem Language Result Execution time Memory
1078038 2024-08-27T11:49:02 Z pcc Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 12368 KB 
#include "circuit.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const int mxn = 2e5+10;

const ll mod = 1000002022;

vector<int> tree[mxn];
int par[mxn];
int N,M;
ll dp[mxn][2];
ll tot = 1;

ll mad(ll a,ll b){
	a += b;
	return a>=mod?a-mod:a;
}
ll mub(ll a,ll b){
	return mad(a,mod-b);
}

pll calc(vector<ll>& a,vector<ll>& b){

	vector<vector<ll>> dp(2,vector<ll>(a.size()+1,0));
	int r = 0;
	int s = a.size();
	dp[r][0] = a[0];
	dp[r][1] = b[0];
	for(int i = 1;i<s;i++){
		r ^= 1;
		fill(dp[r].begin(),dp[r].end(),0);
		for(int j = 0;j<=i+1;j++){
			dp[r][j] = mad(dp[r][j],dp[r^1][j]*a[i]%mod);
			if(j)dp[r][j] = mad(dp[r][j],dp[r^1][j-1]*b[i]%mod);
		}
	}
	for(int i = 1;i<=s;i++){
		dp[r][i] = mad(dp[r][i],dp[r][i-1]);
	}
	ll tot = mad(a[0],b[0]);
	for(int i = 1;i<a.size();i++)tot = tot*mad(a[i],b[i])%mod%mod;
	tot = tot*s%mod;
	pll re = pll(0,0);
	for(int c = 1;c<=s;c++){
		re.fs = mad(re.fs,dp[r][c-1]);
		re.sc = mad(re.sc,mub(dp[r][s],dp[r][c-1]));
	}
	assert(mad(re.fs,re.sc) == tot);
	/*
	cerr<<"CALC: "<<endl;
	for(auto &i:a)cerr<<i<<' ';cerr<<endl;
	for(auto &i:b)cerr<<i<<' ';cerr<<endl;
	for(auto &i:dp[r])cerr<<i<<' ';cerr<<endl;
	cerr<<re.fs<<','<<re.sc<<"::"<<tot<<endl;
	*/
	return re;
}

void dfs(int now){
	if(tree[now].empty())return;
	vector<ll> v1,v2;
	for(auto nxt:tree[now]){
		dfs(nxt);
		v1.push_back(dp[nxt][0]);
		v2.push_back(dp[nxt][1]);
	}
	auto [a,b] = calc(v1,v2);
	tot = tot*v1.size()%mod;
	assert(a<mod&&b<mod);
	dp[now][0] = a,dp[now][1] = b;
	//cerr<<now<<":"<<dp[now][0]<<' '<<dp[now][1]<<endl;
	return;
}

void init(int N1, int M1, std::vector<int> P, std::vector<int> A) {
	N = N1,M = M1;
	for(int i = 1;i<N+M;i++){
		par[i] = P[i];
		tree[par[i]].push_back(i);
	}
	for(int i = 0;i<M;i++){
		dp[i+N][A[i]] = 1;
	}
	dfs(0);
	cerr<<"TOT: "<<tot<<endl;
	assert(tot == mad(dp[0][0],dp[0][1]));
	//for(int i = 0;i<N+M;i++)cerr<<dp[i][0]<<','<<dp[i][1]<<' ';cerr<<endl;
}

void update(int now){
	while(now != 0){
		now = par[now];
		vector<ll> v1,v2;
		for(auto nxt:tree[now]){
			v1.push_back(dp[nxt][0]);
			v2.push_back(dp[nxt][1]);
		}
		auto [a,b] = calc(v1,v2);
		dp[now][0] = a,dp[now][1] = b;
	}
	return;
}

int count_ways(int L, int R) {
	for(int i = L;i<=R;i++){
		dp[i][0] ^= 1;
		dp[i][1] ^= 1;
		update(i);
	}
	//dfs(0);
	//cerr<<"NOW: ";
	//for(int i = N;i<N+M;i++)cerr<<(dp[i][0]?0:1);cerr<<endl;
	return dp[0][1];
}

Compilation message

circuit.cpp: In function 'std::pair<long long int, long long int> calc(std::vector<long long int>&, std::vector<long long int>&)':
circuit.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 1;i<a.size();i++)tot = tot*mad(a[i],b[i])%mod%mod;
      |                ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2569 ms 5208 KB Output is correct
4 Correct 2956 ms 5208 KB Output is correct
5 Correct 2142 ms 5208 KB Output is correct
6 Correct 2737 ms 5208 KB Output is correct
7 Execution timed out 3059 ms 5232 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 5 ms 4952 KB Output is correct
4 Correct 4 ms 4952 KB Output is correct
5 Correct 7 ms 4952 KB Output is correct
6 Correct 4 ms 5208 KB Output is correct
7 Correct 6 ms 5208 KB Output is correct
8 Correct 5 ms 5208 KB Output is correct
9 Correct 9 ms 5208 KB Output is correct
10 Correct 232 ms 5332 KB Output is correct
11 Correct 414 ms 5460 KB Output is correct
12 Correct 7 ms 5208 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2569 ms 5208 KB Output is correct
4 Correct 2956 ms 5208 KB Output is correct
5 Correct 2142 ms 5208 KB Output is correct
6 Correct 2737 ms 5208 KB Output is correct
7 Execution timed out 3059 ms 5232 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 8024 KB Output is correct
2 Correct 1004 ms 11300 KB Output is correct
3 Correct 1065 ms 11292 KB Output is correct
4 Correct 991 ms 12368 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 8024 KB Output is correct
2 Correct 1004 ms 11300 KB Output is correct
3 Correct 1065 ms 11292 KB Output is correct
4 Correct 991 ms 12368 KB Output is correct
5 Execution timed out 3042 ms 9560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 5 ms 4952 KB Output is correct
4 Correct 4 ms 4952 KB Output is correct
5 Correct 7 ms 4952 KB Output is correct
6 Correct 4 ms 5208 KB Output is correct
7 Correct 6 ms 5208 KB Output is correct
8 Correct 5 ms 5208 KB Output is correct
9 Correct 9 ms 5208 KB Output is correct
10 Correct 232 ms 5332 KB Output is correct
11 Correct 414 ms 5460 KB Output is correct
12 Correct 7 ms 5208 KB Output is correct
13 Correct 759 ms 8024 KB Output is correct
14 Correct 1004 ms 11300 KB Output is correct
15 Correct 1065 ms 11292 KB Output is correct
16 Correct 991 ms 12368 KB Output is correct
17 Execution timed out 3042 ms 9560 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2569 ms 5208 KB Output is correct
4 Correct 2956 ms 5208 KB Output is correct
5 Correct 2142 ms 5208 KB Output is correct
6 Correct 2737 ms 5208 KB Output is correct
7 Execution timed out 3059 ms 5232 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 2569 ms 5208 KB Output is correct
4 Correct 2956 ms 5208 KB Output is correct
5 Correct 2142 ms 5208 KB Output is correct
6 Correct 2737 ms 5208 KB Output is correct
7 Execution timed out 3059 ms 5232 KB Time limit exceeded
8 Halted 0 ms 0 KB -