제출 #1222919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222919		abdelhakim	디지털 회로 (IOI22_circuit)	C++20	46 / 100	3037 ms	13832 KiB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
#define ll long long
#define mod 1000002022
#define dbg(x) cerr<<#x << ' ' << x << endl;
using namespace std;
#include <vector>
vector<vector<ll>> adj;
ll n,m;
vector<ll> a;
vector<ll> c;
map<pair<ll,ll>, ll> w;
ll dfs(ll node, ll par)
{
  if(adj[node].size()==1 && node!=par) return 1;
  vector<ll> v(adj[node].size());
  vector<ll> p(adj[node].size());
  vector<ll> s(adj[node].size());
  ll d=adj[node].size()-1;
  if(node==par)d++;
  for (int i=0;i<adj[node].size();i++)
  {
    if(adj[node][i]==par)
    {
      v[i]=1;
      p[i]=v[i];
      if(i>0)p[i]*=p[i-1];
      continue;
    }
    v[i]=dfs(adj[node][i],node);
    p[i]=v[i];
    if(i>0)
    {
      p[i]*=p[i-1];
      p[i]%=mod;
    }
  }
  for (int i=adj[node].size()-1;i>=0;i--)
    {
      s[i]=v[i];
      if(i!=adj[node].size()-1)
      {
        s[i]*=s[i+1];
        s[i]%=mod;
      }
    }
    
    for (int i=0;i<adj[node].size();i++)
    {
      if(adj[node][i]==par)continue;
      ll lft=1;
      ll r=1;
      if(i>0)lft=p[i-1];
      if(i<adj[node].size()-1)r=s[i+1];
      ll val=lft*r%mod;
      w[{node,adj[node][i]}]=val;
      w[{adj[node][i],node}]=val;
    }
  ll pr=p.back()*d%mod;
  return pr;
}
void calculate(ll node, ll par, ll pr)
{
  if(adj[node].size()==1 && node!=par)
  {
    c[node-n]=pr;
    return;
  }
  for (auto &&e : adj[node])
  {
    if(e==par)continue;
   calculate(e,node,pr*w[{node,e}]%mod); 
  }
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n=N;
  m=M;
  c.assign(m,1);
  adj.resize(n+m);
  for (int i=0;i<m;i++)a.push_back(A[i]);
  for (int i=1;i<n+m;i++)
  {
    adj[i].push_back(P[i]);
    adj[P[i]].push_back(i);
  }
  dfs(0,0);
  calculate(0,0,1);
}

int count_ways(int L, int R) {
  ll ans=0;
  for (int i=L;i<=R;i++)
  {
    a[i-n]^=1;
  }
  for (int i=0;i<m;i++)
  {
    ans+=a[i]*c[i];
    ans%=mod;
  }
  return ans;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 28 / 28
• Subtask 8: 0 / 11