답안 #1078530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078530	2024-08-27T19:22:26 Z	ArthuroWich	디지털 회로 (IOI22_circuit)	C++17	9 / 100	3000 ms	8008 KB

circuit

#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[200005];
int p[200005], vis[200005], arr[200005], brr[200005], seg1[4*200005], seg0[4*200005], s[4*200005], dep[200005], mod = 1000002022;
void lazypropagate(int n, int l, int r) {
    if (s[n]) {
        swap(seg1[n], seg0[n]);
        if (l != r) {
            s[2*n] ^= 1;
            s[2*n+1] ^= 1;
        }
        s[n] = 0;
    }
}
void build(int n, int l, int r) {
    if (l == r) {
        seg1[n] = arr[l];
        seg0[n] = brr[l];
    } else {
        int m = (l+r)/2;
        build(2*n, l, m);
        build(2*n+1, m+1, r);
        seg1[n] = seg1[2*n] + seg1[2*n+1];
        seg1[n] %= mod;
        seg0[n] = seg0[2*n] + seg0[2*n+1];
        seg0[n] %= mod;
    }
}
void update(int n, int l, int r, int a, int b) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        s[n] = 1;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        update(2*n, l, m, a, b);
        update(2*n+1, m+1, r, a, b);
        seg1[n] = seg1[2*n] + seg1[2*n+1];
        seg1[n] %= mod;
        seg0[n] = seg0[2*n] + seg0[2*n+1];
        seg0[n] %= mod;
    }
}
int n, m;
void dfs(int i) {
    vis[i] = 1;
    if (i != 0) {
        dfs(p[i]);
    }
}
void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M;
    for (int i = 1; i <= n+m-1; i++) {
        p[i] = P[i];
        adj[P[i]].push_back(i);
    }
    vector<int> b(n+1, 1);
    for (int i = 1; i <= n; i++) {
        b[i] = b[i-1]*2;
        b[i] %= mod;
    }
    dfs(0);
    for (int i = 0; i < m; i++) {
        int v = 1;
        for (int j = 0; j < n; j++) {
            vis[j] = 0;
        }
        dfs(n+i);
        for (int j = 0; j < n; j++) {
            if (vis[j]) {
                continue;
            }
            v *= adj[j].size();
            v %= mod;
        }
        if (A[i]) {
            arr[i] = v;
        } else {
            brr[i] = v;
        }
    }
    build(1, 0, m-1);
}
int count_ways(int L, int R) {
    update(1, 0, m-1, L-n, R-n);
    return seg1[1];
}

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	3 ms	5056 KB	Output is correct
3	Correct	4 ms	5208 KB	Output is correct
4	Correct	2 ms	5208 KB	Output is correct
5	Correct	2 ms	5208 KB	Output is correct
6	Correct	2 ms	5208 KB	Output is correct
7	Correct	3 ms	5124 KB	Output is correct
8	Correct	2 ms	5208 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4952 KB	Output is correct
2	Correct	3 ms	5208 KB	Output is correct
3	Correct	4 ms	5208 KB	Output is correct
4	Correct	3 ms	5208 KB	Output is correct
5	Correct	3 ms	5208 KB	Output is correct
6	Correct	5 ms	5208 KB	Output is correct
7	Correct	7 ms	5232 KB	Output is correct
8	Correct	9 ms	5208 KB	Output is correct
9	Correct	7 ms	5208 KB	Output is correct
10	Correct	6 ms	5208 KB	Output is correct
11	Correct	6 ms	5208 KB	Output is correct
12	Correct	6 ms	5208 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	3 ms	5056 KB	Output is correct
3	Correct	4 ms	5208 KB	Output is correct
4	Correct	2 ms	5208 KB	Output is correct
5	Correct	2 ms	5208 KB	Output is correct
6	Correct	2 ms	5208 KB	Output is correct
7	Correct	3 ms	5124 KB	Output is correct
8	Correct	2 ms	5208 KB	Output is correct
9	Correct	4 ms	4952 KB	Output is correct
10	Correct	3 ms	5208 KB	Output is correct
11	Correct	4 ms	5208 KB	Output is correct
12	Correct	3 ms	5208 KB	Output is correct
13	Correct	3 ms	5208 KB	Output is correct
14	Correct	5 ms	5208 KB	Output is correct
15	Correct	7 ms	5232 KB	Output is correct
16	Correct	9 ms	5208 KB	Output is correct
17	Correct	7 ms	5208 KB	Output is correct
18	Correct	6 ms	5208 KB	Output is correct
19	Correct	6 ms	5208 KB	Output is correct
20	Correct	6 ms	5208 KB	Output is correct
21	Incorrect	5 ms	5208 KB	1st lines differ - on the 1st token, expected: '759476520', found: '481963316'
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3056 ms	8008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	3056 ms	8008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4952 KB	Output is correct
2	Correct	3 ms	5208 KB	Output is correct
3	Correct	4 ms	5208 KB	Output is correct
4	Correct	3 ms	5208 KB	Output is correct
5	Correct	3 ms	5208 KB	Output is correct
6	Correct	5 ms	5208 KB	Output is correct
7	Correct	7 ms	5232 KB	Output is correct
8	Correct	9 ms	5208 KB	Output is correct
9	Correct	7 ms	5208 KB	Output is correct
10	Correct	6 ms	5208 KB	Output is correct
11	Correct	6 ms	5208 KB	Output is correct
12	Correct	6 ms	5208 KB	Output is correct
13	Execution timed out	3056 ms	8008 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	3 ms	5056 KB	Output is correct
3	Correct	4 ms	5208 KB	Output is correct
4	Correct	2 ms	5208 KB	Output is correct
5	Correct	2 ms	5208 KB	Output is correct
6	Correct	2 ms	5208 KB	Output is correct
7	Correct	3 ms	5124 KB	Output is correct
8	Correct	2 ms	5208 KB	Output is correct
9	Correct	4 ms	4952 KB	Output is correct
10	Correct	3 ms	5208 KB	Output is correct
11	Correct	4 ms	5208 KB	Output is correct
12	Correct	3 ms	5208 KB	Output is correct
13	Correct	3 ms	5208 KB	Output is correct
14	Correct	5 ms	5208 KB	Output is correct
15	Correct	7 ms	5232 KB	Output is correct
16	Correct	9 ms	5208 KB	Output is correct
17	Correct	7 ms	5208 KB	Output is correct
18	Correct	6 ms	5208 KB	Output is correct
19	Correct	6 ms	5208 KB	Output is correct
20	Correct	6 ms	5208 KB	Output is correct
21	Incorrect	5 ms	5208 KB	1st lines differ - on the 1st token, expected: '759476520', found: '481963316'
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4952 KB	Output is correct
2	Correct	3 ms	5056 KB	Output is correct
3	Correct	4 ms	5208 KB	Output is correct
4	Correct	2 ms	5208 KB	Output is correct
5	Correct	2 ms	5208 KB	Output is correct
6	Correct	2 ms	5208 KB	Output is correct
7	Correct	3 ms	5124 KB	Output is correct
8	Correct	2 ms	5208 KB	Output is correct
9	Correct	4 ms	4952 KB	Output is correct
10	Correct	3 ms	5208 KB	Output is correct
11	Correct	4 ms	5208 KB	Output is correct
12	Correct	3 ms	5208 KB	Output is correct
13	Correct	3 ms	5208 KB	Output is correct
14	Correct	5 ms	5208 KB	Output is correct
15	Correct	7 ms	5232 KB	Output is correct
16	Correct	9 ms	5208 KB	Output is correct
17	Correct	7 ms	5208 KB	Output is correct
18	Correct	6 ms	5208 KB	Output is correct
19	Correct	6 ms	5208 KB	Output is correct
20	Correct	6 ms	5208 KB	Output is correct
21	Incorrect	5 ms	5208 KB	1st lines differ - on the 1st token, expected: '759476520', found: '481963316'
22	Halted	0 ms	0 KB	-

답안 #1078530

Compilation message