Submission #639359

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
639359	2022-09-09 16:18:22	CSQ31	Digital Circuit (IOI22_circuit)	C++17	46 / 100	1053 ms	14064 KiB

circuit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll MOD = 1000002022;
const int MAXN = 1e5+5;
vector<int>adj[MAXN];
ll c[MAXN],sub[MAXN];
int n,m;
void dfs(int v){
  if(adj[v].empty())sub[v] = 1;
  else sub[v] = adj[v].size();
  for(int x:adj[v]){
    dfs(x);
    sub[v] = sub[v]*sub[x]%MOD;
  }
  
}
void dfs(int v,ll cur){
  if(adj[v].empty()){
    c[v-n] = cur;
    return;
  }
  int s = adj[v].size();
  vector<ll>pref(s,1),suff(s,1);
  for(int i=0;i<s;i++){
    pref[i] = sub[adj[v][i]];
    suff[i] = sub[adj[v][i]];
    if(i)pref[i] = pref[i]*pref[i-1]%MOD;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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