제출 #836240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836240		Trumling	Digital Circuit (IOI22_circuit)	C++17	0 / 100	13 ms	8232 KiB

circuit

    #include "circuit.h"
    #include<bits/stdc++.h>
    using namespace std;
     
    #define F first
    #define S second
    #define all(x) x.begin(),x.end()
    typedef long long ll;
    #define pb push_back
    #define MOD 1000002022
     
    vector<ll>r;
    ll m,n;
    vector<vector<int>>g;
    vector<pair<ll,ll>> tree;
    vector<int>a;
    void build(int start)
    {
      if(g[start].size()==1)
      {
        if(a[start])
        tree[start].F=1;
        else
        tree[start].S=1;

        return ;
      }
      ll l,r;
      for(auto x:g[start])
      if(x>start)
      build(x);

      l=g[start][1];
      r=g[start][2];

      tree[start].F=((tree[l].F*tree[r].F)%MOD  + (tree[l].F*(tree[r].F+tree[r].S))%MOD + (tree[l].S*tree[r].F)%MOD)%MOD;
      tree[start].S=((tree[l].S*(tree[r].F+tree[r].S))%MOD + (tree[l].F*tree[r].S)%MOD + (tree[l].S*tree[r].S)%MOD)%MOD;

      return ;
    }

    void init(int N, int M, vector<int> P, vector<int> A) 
    {
      n=N;
      m=M;
      tree.assign(n+m,{0,0});
      g.assign(N,vector<int>());
      a.assign(N+M,0);

      for(int i=0;i<m;i++)
      a[i+n]=A[i];

      

      for(int i=1;i<N+M;i++)
      {
        g[i].pb(P[i]);
        g[P[i]].pb(i);
      }
    }
     
    int count_ways(int L, int R) 
    {
      for(int i=L;i<R;i++)
        a[i]=1-a[i];
      
      build(0);
      return (tree[0].F+tree[0].S)%MOD;
    }

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