oj.uz

Submission #876354

# Submission time Handle Problem Language Result Execution time Memory
876354 2023-11-21T15:33:03 Z Halfjuice Digital Circuit (IOI22_circuit) C++17
2 / 100
 406 ms 5808 KB 
#include <iostream>
 
#include <vector>
 
using namespace std;
 
long modPow(long b, long e, long m)
{
    b = b%m;
    long r = 1;
    while (e>0) {
        if (e%2 == 1) {
            r = (r*b) % m;
        }
        b = (b*b)%m;
        e >>= 1;
    }
    return r;
}
 
#define MOD 1000002022
 
typedef struct _Node {
    _Node* parent;
    vector<_Node*> children;
    
    int index;
    int internalNodeCount;
    int internalNodeComb;
    long contribCount;
  
    void initAny() {
        internalNodeCount = 0;
        internalNodeComb = 1;
        contribCount = 0;
    
        for (auto it=children.begin(); it!=children.end(); ++it) {
            (*it)->initAny();
            if ((*it)->children.size() > 0) {
                internalNodeCount += (*it)->internalNodeCount;
                internalNodeComb = (internalNodeComb * (*it)->children.size()) % MOD;
            }
        }
        if (children.size() > 0) {
            internalNodeCount += 1;
            internalNodeComb = (internalNodeComb * children.size()) % MOD;
        }
    }
  
    long searchPathUp(_Node* child) {
        if (!parent && index != 0) {
            return 0;
        }
        long res = 1;
        for (auto it=children.begin(); it!=children.end(); ++it) {
            if (*it != child) {
                res = (res * (*it)->internalNodeComb) % MOD;
            }
        }
        if (parent) {
            res = (res*parent->searchPathUp(this)) % MOD;
        }
        return res;
    }
    
    void print() {
        //cout << "N" << index << " C=" << children.size() << " IC=" << internalNodeCount << " Ct=" << contribCount << endl;
    }
  
    void initLeaf() {
        if (this->children.size() == 0) {
            contribCount = parent->searchPathUp(this);
        }
    }
} Node;
 
vector<Node> nodes;
vector<int> state;
long cur;
int n, m;
 
//#define DEBUG_PRINT(nodes) for (int i=0; i<N+M; i++) nodes[i].print(); 
#define DEBUG_PRINT(nodes)
 
void init(int N, int M, vector<int> P, vector<int> A) {
    n = N;
    m = M;
    nodes.empty();
    for (int i=0; i<N+M; i++) {
        nodes.push_back(Node());
    }
    for (int i=0; i<N+M; i++) {
        if (P[i] == -1) {
            nodes[i].parent = 0;
        } else {
            nodes[i].parent = &(nodes[P[i]]);
            nodes[P[i]].children.push_back(&(nodes[i]));
            nodes[i].index = i;
        }
    }
    
    DEBUG_PRINT(nodes)
    nodes[0].initAny();
    DEBUG_PRINT(nodes)
  
    for (int i=N; i<N+M; i++) {
        nodes[i].initLeaf();
    }
    
    DEBUG_PRINT(nodes)
    
    state = A;
    cur = 0;
    for (int i=0; i<M; i++) {
        cur = (cur + nodes[N+i].contribCount*state[i]) % MOD;
    }
}
 
int count_ways(int L, int R) {
    for (int i=L; i<=R; i++) {
        if (state[i-n]) {
            state[i-n] = 0;
            cur = (cur - nodes[i].contribCount) % MOD;
        } else {
            state[i-n] = 1;
            cur = (cur + nodes[i].contribCount) % MOD;
        }
    }
    if (cur < 0) {
        cur = cur + MOD;
    }
    return cur;
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:88:16: warning: ignoring return value of 'bool std::vector<_Tp, _Alloc>::empty() const [with _Tp = _Node; _Alloc = std::allocator<_Node>]', declared with attribute 'nodiscard' [-Wunused-result]
   88 |     nodes.empty();
      |     ~~~~~~~~~~~^~
In file included from /usr/include/c++/10/vector:67,
                 from circuit.cpp:3:
/usr/include/c++/10/bits/stl_vector.h:1007:7: note: declared here
 1007 |       empty() const _GLIBCXX_NOEXCEPT
      |       ^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 5 ms 560 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '67108864'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 5 ms 560 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '67108864'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 406 ms 5808 KB 1st lines differ - on the 1st token, expected: '431985922', found: '253724586'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 406 ms 5808 KB 1st lines differ - on the 1st token, expected: '431985922', found: '253724586'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '67108864'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 5 ms 560 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '67108864'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 5 ms 560 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '52130940', found: '67108864'
11 Halted 0 ms 0 KB -