oj.uz

답안 #1077388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077388 2024-08-27T06:33:33 Z UmairAhmadMirza 디지털 회로 (IOI22_circuit) C++17
11 / 100
 3000 ms 23636 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=3e5+5;
ll const mod=1000002022;
vector<int> child[N];
ll on[N],off[N],tot[N];
vector<ll> dp[N];
int n,m;
vector<int> par,st;
int dep[N];
void dfs(int node){
	for(int i:child[node]){
		dep[i]=dep[node]+1;
		dfs(i);
	}
}
bool vis[N];

void compute(int node){
	int c=child[node].size();
	tot[node]=c;
	for(int i:child[node])
		tot[node]=(tot[node]*tot[i])%mod;
	for (int i = 0; i <=c+2; ++i)
	{
		dp[i].clear();
		dp[i].resize(c+5,0);
	}
	dp[1][1]=on[child[node][0]];
	dp[1][0]=off[child[node][0]];
	for(int i=2;i<=c;i++){
		for(int j=0;j<=i;j++)
		{
			dp[i][j]=(dp[i-1][j]*off[child[node][i-1]])%mod;
			if(j==0)
				continue;
			dp[i][j]+=((dp[i-1][j-1]*on[child[node][i-1]])%mod);
			dp[i][j]%=mod;
		}
		// cout<<endl;
	}
	on[node]=0;
	for(ll i=1;i<=c;i++)
		on[node]=(on[node]+((dp[c][i]*i)%mod))%mod;
	off[node]=(((tot[node]-on[node]))+mod)%mod;
}

void init(int nn, int mm, vector<int> P, vector<int> A){
	// cerr<<"GOT"<<endl;
	n=nn;
	m=mm;
	par=P;
	st=A;
	for(int i=1;i<n+m;i++)
		child[par[i]].push_back(i);
	dfs(0);
	priority_queue<pair<int,int>> q;
	for(int i=n;i<n+m;i++){
		tot[i]=1;
		if(st[i-n]==1){
			on[i]=1;
			off[i]=0;
		}
		else{
			on[i]=0;
			off[i]=1;
		}
		// cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl;
	}
	for(int i=0;i<n+m;i++)
		q.push({dep[par[i]],par[i]});
	while(q.size()){
		int node=(q.top()).second;
		q.pop();
		if(node==-1 || vis[node])
			continue;
		vis[node]=1;
		compute(node);
		q.push({dep[par[node]],par[node]});
	}
	// for (int i = 0; i < n; ++i)
		// cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl;
}
int count_ways(int L, int R){
	// cout<<"L R := "<<L<<' '<<R<<endl;
	// for (int i = 0; i < n+m; ++i)
	// 	vis[i]=0;
	priority_queue<pair<int,int>> q;
	for(int i=L;i<=R;i++){
		st[i-n]^=1;
		tot[i]=1;
		if(st[i-n]==1){
			on[i]=1;
			off[i]=0;
		}
		else{
			on[i]=0;
			off[i]=1;
		}
		q.push({dep[par[i]],par[i]});
	}
	while(q.size()){
		int node=(q.top()).second;
		q.pop();
		if(node==-1)
			continue;
		// vis[node]=1;
		// cout<<node<<endl;
		compute(node);
		q.push({dep[par[node]],par[node]});
	}
	// for (int i = 0; i < n+m; ++i)
	// 	cout<<on[i]<<' '<<off[i]<<' '<<tot[i]<<endl;
	return on[0]%mod;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 8 ms 14424 KB Output is correct
3 Execution timed out 3097 ms 22084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 7 ms 14424 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 9 ms 14424 KB Output is correct
6 Correct 8 ms 14424 KB Output is correct
7 Correct 9 ms 14680 KB Output is correct
8 Correct 9 ms 14680 KB Output is correct
9 Correct 11 ms 14528 KB Output is correct
10 Correct 123 ms 14680 KB Output is correct
11 Correct 242 ms 14712 KB Output is correct
12 Correct 8 ms 14680 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 8 ms 14424 KB Output is correct
3 Execution timed out 3097 ms 22084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 19152 KB Output is correct
2 Correct 950 ms 23500 KB Output is correct
3 Correct 1012 ms 23500 KB Output is correct
4 Correct 1010 ms 23636 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 19152 KB Output is correct
2 Correct 950 ms 23500 KB Output is correct
3 Correct 1012 ms 23500 KB Output is correct
4 Correct 1010 ms 23636 KB Output is correct
5 Execution timed out 3023 ms 19160 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 7 ms 14424 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 7 ms 14424 KB Output is correct
5 Correct 9 ms 14424 KB Output is correct
6 Correct 8 ms 14424 KB Output is correct
7 Correct 9 ms 14680 KB Output is correct
8 Correct 9 ms 14680 KB Output is correct
9 Correct 11 ms 14528 KB Output is correct
10 Correct 123 ms 14680 KB Output is correct
11 Correct 242 ms 14712 KB Output is correct
12 Correct 8 ms 14680 KB Output is correct
13 Correct 619 ms 19152 KB Output is correct
14 Correct 950 ms 23500 KB Output is correct
15 Correct 1012 ms 23500 KB Output is correct
16 Correct 1010 ms 23636 KB Output is correct
17 Execution timed out 3023 ms 19160 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 8 ms 14424 KB Output is correct
3 Execution timed out 3097 ms 22084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 8 ms 14424 KB Output is correct
3 Execution timed out 3097 ms 22084 KB Time limit exceeded
4 Halted 0 ms 0 KB -