| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 995378 | aaaaaarroz | Digital Circuit (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int mod=1000002022;
vector<vector<int>>graph;
vector<int>max_parameter;
vector<int>ways;
vector<int>state;
int n,m;
void dfs1(int nodo){
if(nodo>=n){
return;
}
for(int vecino:graph[nodo]){
dfs1(vecino);
if(vecino<n){
max_parameter[nodo]+=(max_parameter[vecino]>=1?1:0);
}
else{
max_parameter[nodo]+=(state[vecino-n]==1?1:0);
}
}
}
void dfs2(int nodo){
if(nodo<n){
ways[nodo]=max_parameter[nodo];
}
else{
return;
}
for(int vecino:graph[nodo]){
dfs2(vecino);
if(ways[vecino]){
(ways[nodo]*=ways[vecino])%=mod;
}
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n=N;
m=M;
graph.resize(N+M,vector<int>());
state=A;
max_parameter.resize(N,0);
ways.resize(N+M,0);
for(int i=0;i<P.size();i++){
if(P[i]!=-1){
graph[P[i]].push_back(i);
}
}
}
int count_ways(int L, int R) {
for(int i=L;i<=R;i++){
if(state[i-n]==0){
state[i-n]=1;
}
else{
state[i-n]=0;
}
}
max_parameter.resize(n,0);
dfs1(0);
ways.resize(n+m,1);
dfs2(0);
return ways[0];
}
int main() {
int N, M, Q;
cin>>N>>M>>Q;
vector<int> P(N + M), A(M);
for (int i = 0; i < N + M; ++i) {
cin>>P[i];
}
for (int j = 0; j < M; ++j) {
cin>>A[j];
}
init(N, M, P, A);
for (int i = 0; i < Q; ++i) {
int L, R;
cin>>L>>R;
cout<<count_ways(L, R)<<"\n";
cerr<<"\n";
}
return 0;
}