Submission #787538

#	Time	Username	Problem	Language	Result	Execution time	Memory
787538		thimote75	디지털 회로 (IOI22_circuit)	C++17	18 / 100	3035 ms	3364 KiB

circuit

#include "circuit.h"

#include <bits/stdc++.h>
#define num long long

using namespace std;
const int MOD = 1000002022;

using idata = vector<int>;
using ndata = vector<num>;
using igrid = vector<idata>;

ndata C;

idata status;
idata target;
igrid roads;

int N, M;

void init(int _N, int _M, idata P, idata A) {
  N = _N; M = _M;
  C    .resize(N);

  roads.resize(N);

  for (int i = 1; i < N + M; i ++)
    roads[P[i]].push_back(i);

  status = A;
  target.resize(M);
  for (int i = 0; i < M; i ++)
    target[i] = P[i + N];

  for (int i = 1; i < N + M; i ++) C[P[i]] ++;
}

pair<num, num> dfs (int node) {
  if (node >= N)
    return { 1 - status[node - N], status[node - N] };

  ndata grid(C[node] + 1, 0);
  grid[0] = 1;

  for (int next : roads[node]) {
    pair<num, num> res = dfs(next);

    for (int i = grid.size() - 1; i >= 0; i --) {
      if (i + 1 != grid.size()) {
        grid[i + 1] += grid[i] * res.second;
        grid[i + 1] %= MOD;
      }

      grid[i] *= res.first; grid[i] %= MOD;
    }
  }

  pair<num, num> result = { 0, 0 };
  for (int i = 1; i < grid.size(); i ++) {
    result.second += i * grid[i];
    result.second %= MOD;

    result.first += (grid.size() - i) * grid[i - 1];
    result.first %= MOD;
  }

  return result;
}

int count_ways(int L, int R) {
  L -= N; R -= N;
  for (int i = L; i <= R; i ++)
    status [i] = 1 - status[i];
  
  return dfs(0).second;
}

Compilation message (stderr)

circuit.cpp: In function 'std::pair<long long int, long long int> dfs(int)':
circuit.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |       if (i + 1 != grid.size()) {
      |           ~~~~~~^~~~~~~~~~~~~~
circuit.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 1; i < grid.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~

• 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: 0 / 28
• Subtask 8: 0 / 11