oj.uz

답안 #1080750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1080750 2024-08-29T13:41:02 Z LittleOrange 디지털 회로 (IOI22_circuit) C++17
11 / 100
 3000 ms 9048 KB 
#include "circuit.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000002022;
ll n,m;
vector<ll> p,a;
vector<vector<ll>> con;
vector<pair<ll,ll>> stat;
void dfs(ll);
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n=N;
  m=M;
  p.assign(P.begin(),P.end());
  a.assign(A.begin(),A.end());
  con.resize(n);
  for(ll i = 1;i<n+m;i++) con[p[i]].push_back(i);
  stat.resize(n+m);
  dfs(0);
}
void upd(ll i){
  if (i>=n){
    stat[i] = {a[i-n]==0,a[i-n]==1};
    return;
  }
  ll c = con[i].size();
  vector<ll> v(c+1,0),v0(c+1,0);
  v[0] = 1;
  for(ll j : con[i]){
    auto [x,y] = stat[j];
    for(ll i = 0;i<c;i++){
      v0[i] += v[i]*x%mod;
      v0[i+1] += v[i]*y%mod;
    }
    v.swap(v0);
    fill(v0.begin(),v0.end(),0);
  }
  ll x = 0, y = 0;
  for(ll j = 0;j<=c;j++){
    x += v[j]*(c-j)%mod;
    y += v[j]*j%mod;
  }
  stat[i] = {x%mod,y%mod};
}
void dfs(ll i){// 0, 1
  if(i<n) for(ll j : con[i]) dfs(j);
  upd(i);
}
int count_ways(int L, int R) {
  for(ll i = L;i<=R;i++) {
    a[i-n]^=1;
    ll x = i;
    upd(x);
    while (x){
      x = p[x];
      upd(x);
    }
  }
  return stat[0].second;
}

Subtask #1
0 / 2.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 500 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 86 ms 344 KB Output is correct
11 Correct 136 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 566 ms 4696 KB Output is correct
2 Correct 821 ms 9048 KB Output is correct
3 Correct 855 ms 9048 KB Output is correct
4 Correct 833 ms 9048 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 566 ms 4696 KB Output is correct
2 Correct 821 ms 9048 KB Output is correct
3 Correct 855 ms 9048 KB Output is correct
4 Correct 833 ms 9048 KB Output is correct
5 Execution timed out 3048 ms 4828 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 500 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 86 ms 344 KB Output is correct
11 Correct 136 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 566 ms 4696 KB Output is correct
14 Correct 821 ms 9048 KB Output is correct
15 Correct 855 ms 9048 KB Output is correct
16 Correct 833 ms 9048 KB Output is correct
17 Execution timed out 3048 ms 4828 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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