oj.uz

Submission #1078036

# Submission time Handle Problem Language Result Execution time Memory
1078036 2024-08-27T11:48:02 Z pcc Digital Circuit (IOI22_circuit) C++17
11 / 100
 3000 ms 13656 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){

	assert(a.size()<=2);
	if(a.size() == 1)return pll(a[0],b[0]);
	ll ta = mad(a[0]*a[1]*2%mod,mad(a[0]*b[1]%mod,a[1]*b[0]%mod));
	ll tb = mad(b[0]*b[1]*2%mod,mad(a[0]*b[1]%mod,a[1]*b[0]%mod));
	return pll(ta,tb);

	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:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Runtime error 7 ms 13656 KB Execution killed with signal 6
4 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 2 ms 5048 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 4 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 3 ms 6744 KB Output is correct
9 Correct 5 ms 5208 KB Output is correct
10 Correct 103 ms 5356 KB Output is correct
11 Correct 178 ms 5208 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Runtime error 7 ms 13656 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 8024 KB Output is correct
2 Correct 875 ms 11096 KB Output is correct
3 Correct 868 ms 11088 KB Output is correct
4 Correct 861 ms 11288 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 8024 KB Output is correct
2 Correct 875 ms 11096 KB Output is correct
3 Correct 868 ms 11088 KB Output is correct
4 Correct 861 ms 11288 KB Output is correct
5 Execution timed out 3033 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 2 ms 5048 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 4 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 3 ms 6744 KB Output is correct
9 Correct 5 ms 5208 KB Output is correct
10 Correct 103 ms 5356 KB Output is correct
11 Correct 178 ms 5208 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 621 ms 8024 KB Output is correct
14 Correct 875 ms 11096 KB Output is correct
15 Correct 868 ms 11088 KB Output is correct
16 Correct 861 ms 11288 KB Output is correct
17 Execution timed out 3033 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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Runtime error 7 ms 13656 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Runtime error 7 ms 13656 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -