oj.uz

Submission #638748

# Submission time Handle Problem Language Result Execution time Memory
638748 2022-09-07T09:05:30 Z maomao90 Digital Circuit (IOI22_circuit) C++17
50 / 100
 1028 ms 29556 KB 
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define submod(x) if (x >= MOD) x -= MOD
#define addmod(x) if (x < 0) x += MOD

const int MAXN = 200005;
const int INF = 1000000007;
const ll LINF = 1000000000000000007;
const int MOD = 1000002022;

namespace brute {
    int n, m;
    vi p, a;
    vi adj[MAXN];

    ll ways[MAXN];
    ll dfs(int u) {
	if (u >= n) {
	    ways[u] = 1;
	    return a[u - n];
	}
	vll dp(1, 1);
	ways[u] = SZ(adj[u]);
	for (int v : adj[u]) {
	    ll tmp = dfs(v);
	    vll ndp(SZ(dp) + 1, 0);
	    REP (i, 0, SZ(dp)) {
		ndp[i + 1] += dp[i] * tmp % MOD;
		submod(ndp[i + 1]);
	    }
	    REP (i, 0, SZ(dp)) {
		ndp[i] += dp[i] * (ways[v] - tmp + MOD) % MOD;
		submod(ndp[i]);
	    }
	    dp = ndp;
	    ways[u] = ways[u] * ways[v] % MOD;
	}
	ll res = 0;
	REP (i, 1, SZ(dp)) {
	    res += dp[i] * i % MOD;
	    submod(res);
	}
	return res;
    }

    void init(int N, int M, vi P, vi A) {
	n = N, m = M, p = P, a = A;
	REP (i, 1, n + m) {
	    adj[p[i]].pb(i);
	}
    }

    int count_ways(int L, int R) {
	int l = L, r = R;
	REP (i, l - n, r + 1 - n) {
	    a[i] ^= 1;
	}
	return dfs(0);
    }
}

int n, m;
vi p, a;
vi adj[MAXN];

ll ways[MAXN];
void dfs(int u) {
    ways[u] = max(1, SZ(adj[u]));
    for (int v : adj[u]) {
	dfs(v);
	ways[u] = ways[u] * ways[v] % MOD;
    }
}
ll pw[MAXN];
void dfs2(int u) {
    if (adj[u].empty()) {
	return;
    }
    assert(SZ(adj[u]) == 2);
    REP (i, 0, 2) {
	pw[adj[u][i]] = ways[adj[u][i ^ 1]] * pw[u] % MOD;
	dfs2(adj[u][i]);
    }
}

#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
int sm[MAXN * 4], lz[MAXN * 4];
ll coef[MAXN * 4];
void propo(int u, int lo, int hi) {
    if (lo == hi || lz[u] == 0) return;
    MLR;
    sm[lc] = coef[lc] - sm[lc];
    addmod(sm[lc]);
    sm[rc] = coef[rc] - sm[rc];
    addmod(sm[rc]);
    lz[lc] ^= 1;
    lz[rc] ^= 1;
    lz[u] = 0;
}
void init(int u = 1, int lo = 0, int hi = m - 1) {
    if (lo == hi) {
	coef[u] = pw[lo + n];
	sm[u] = a[lo] * coef[u] % MOD;
	lz[u] = 0;
	return;
    }
    MLR;
    init(lc, lo, mid);
    init(rc, mid + 1, hi);
    sm[u] = sm[lc] + sm[rc];
    submod(sm[u]);
    coef[u] = coef[lc] + coef[rc];
    submod(coef[u]);
}
void upd(int s, int e, int u = 1, int lo = 0, int hi = m - 1) {
    if (lo >= s && hi <= e) {
	lz[u] ^= 1;
	sm[u] = coef[u] - sm[u];
	addmod(sm[u]);
	return;
    }
    propo(u, lo, hi);
    MLR;
    if (s <= mid) {
	upd(s, e, lc, lo, mid);
    }
    if (e > mid) {
	upd(s, e, rc, mid + 1, hi);
    }
    sm[u] = sm[lc] + sm[rc];
    submod(sm[u]);
}

void init(int N, int M, vi P, vi A) {
    n = N, m = M, p = P, a = A;
    if (N <= 1000 && M <= 1000 && 0) {
	brute::init(N, M, P, A);
	return;
    }
    REP (i, 1, n + m) {
	adj[p[i]].pb(i);
    }
    dfs(0);
    pw[0] = 1;
    dfs2(0);
    REP (i, n, n + m) {
	cerr << i << ": " << pw[i] << '\n';
    }
    init();
    //brute::init(N, M, P, A);
}

int count_ways(int L, int R) {
    if (n <= 1000 && m <= 1000 && 0) {
	return brute::count_ways(L, R);
    }
    int l = L, r = R;
    upd(l - n, r - n);
    //assert(sm[1] == brute::count_ways(L, R));
    return sm[1];
}

Compilation message

circuit.cpp: In function 'void propo(int, int, int)':
circuit.cpp:113:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
circuit.cpp:118:5: note: in expansion of macro 'MLR'
  118 |     MLR;
      |     ^~~
circuit.cpp:113:17: warning: unused variable 'mid' [-Wunused-variable]
  113 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
circuit.cpp:118:5: note: in expansion of macro 'MLR'
  118 |     MLR;
      |     ^~~
circuit.cpp: In function 'void init(int, int, int)':
circuit.cpp:113:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
circuit.cpp:134:5: note: in expansion of macro 'MLR'
  134 |     MLR;
      |     ^~~
circuit.cpp: In function 'void upd(int, int, int, int, int)':
circuit.cpp:113:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
circuit.cpp:150:5: note: in expansion of macro 'MLR'
  150 |     MLR;
      |     ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Runtime error 13 ms 19476 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 7 ms 9680 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 7 ms 9680 KB Output is correct
5 Correct 7 ms 9680 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 5 ms 9808 KB Output is correct
8 Correct 5 ms 9808 KB Output is correct
9 Correct 6 ms 9784 KB Output is correct
10 Correct 5 ms 9808 KB Output is correct
11 Correct 6 ms 9840 KB Output is correct
12 Correct 5 ms 9808 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Runtime error 13 ms 19476 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 13808 KB Output is correct
2 Correct 1028 ms 17884 KB Output is correct
3 Correct 601 ms 17864 KB Output is correct
4 Correct 989 ms 17880 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 13808 KB Output is correct
2 Correct 1028 ms 17884 KB Output is correct
3 Correct 601 ms 17864 KB Output is correct
4 Correct 989 ms 17880 KB Output is correct
5 Correct 786 ms 13776 KB Output is correct
6 Correct 968 ms 17864 KB Output is correct
7 Correct 942 ms 17904 KB Output is correct
8 Correct 970 ms 17908 KB Output is correct
9 Correct 478 ms 9936 KB Output is correct
10 Correct 821 ms 10192 KB Output is correct
11 Correct 955 ms 10192 KB Output is correct
12 Correct 858 ms 10192 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 7 ms 9680 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 7 ms 9680 KB Output is correct
5 Correct 7 ms 9680 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 5 ms 9808 KB Output is correct
8 Correct 5 ms 9808 KB Output is correct
9 Correct 6 ms 9784 KB Output is correct
10 Correct 5 ms 9808 KB Output is correct
11 Correct 6 ms 9840 KB Output is correct
12 Correct 5 ms 9808 KB Output is correct
13 Correct 636 ms 13808 KB Output is correct
14 Correct 1028 ms 17884 KB Output is correct
15 Correct 601 ms 17864 KB Output is correct
16 Correct 989 ms 17880 KB Output is correct
17 Correct 786 ms 13776 KB Output is correct
18 Correct 968 ms 17864 KB Output is correct
19 Correct 942 ms 17904 KB Output is correct
20 Correct 970 ms 17908 KB Output is correct
21 Correct 478 ms 9936 KB Output is correct
22 Correct 821 ms 10192 KB Output is correct
23 Correct 955 ms 10192 KB Output is correct
24 Correct 858 ms 10192 KB Output is correct
25 Correct 813 ms 23148 KB Output is correct
26 Correct 870 ms 23296 KB Output is correct
27 Correct 913 ms 23240 KB Output is correct
28 Correct 703 ms 23240 KB Output is correct
29 Correct 981 ms 29556 KB Output is correct
30 Correct 821 ms 29516 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Runtime error 13 ms 19476 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Runtime error 13 ms 19476 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -