Submission #1235789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235789		kilikuma	JOI tour (JOI24_joitour)	C++20	0 / 100	45 ms	21540 KiB

joitour

#include "joitour.h"
#include <bits/stdc++.h>

using namespace std; 

const int n = (1 << 17);  

struct Node {

  long long rep = 0; 
  long long nb0 = 0; 
  long long nb1 = 0; 
  long long nb2 = 0; 
  long long nb10 = 0; 
  long long nb12 = 0; 
  long long nb01 = 0;
  long long nb21 = 0; 

}; 

vector<Node> dp; 

void combine(int node) {
  dp[node].nb0 = dp[2 * node].nb0 + dp[2 * node + 1].nb0; 
  dp[node].nb1 = dp[2 * node].nb1 + dp[2 * node + 1].nb1;
  dp[node].nb2 = dp[2 * node].nb2 + dp[2 * node + 1].nb2;
  dp[node].nb01 = (dp[2 * node].nb01 + dp[2 * node + 1].nb01) + (dp[2 * node].nb0 * dp[2 * node + 1].nb1); 
  dp[node].nb21 = (dp[2 * node].nb21 + dp[2 * node + 1].nb21) + (dp[2 * node].nb2 * dp[2 * node + 1].nb1);
  dp[node].nb10 = (dp[2 * node].nb10 + dp[2 * node + 1].nb10) + (dp[2 * node].nb1 * dp[2 * node + 1].nb0);
  dp[node].nb12 = (dp[2 * node].nb12 + dp[2 * node + 1].nb12) + (dp[2 * node].nb1 * dp[2 * node + 1].nb2);
  dp[node].rep = (dp[2 * node].rep + dp[2 * node + 1].rep) + (dp[2 * node].nb0 * dp[2 * node + 1].nb12) + (dp[2 * node].nb2 * dp[2 * node + 1].nb10) + (dp[2 * node].nb21 * dp[2 * node + 1].nb0) + (dp[2 * node].nb01 * dp[2 * node + 1].nb2); 
  return; 
}

void init(int N, vector<int> f, vector<int> u, vector<int> v, int q) {
  dp.resize(2 * n); 
  for (int i = 0; i < N; i ++) {
    Node nouv; 
    dp[n + i] = nouv; 
    if (f[i] == 0) {
      dp[n + i].nb0 = 1; 
    } 
    if (f[i] == 1) {
      dp[n + i].nb1 = 1; 
    }
    if (f[i] == 2) {
      dp[n + i].nb2 = 1; 
    }
  }
  for (int j = n - 1; j >= 1; j --) {
    combine(j); 
  }
}

void change(int x, int y) {
  Node nouv; 
  dp[n + x] = nouv; 
  if (y == 0) {
    dp[n + x].nb0 = 1; 
  }
  if (y == 1) {
    dp[n + x].nb1 = 1; 
  }
  if (y == 2) {
    dp[n + x].nb2 = 1; 
  }
  for (int cur = (n + x) / 2; cur > 0; cur /= 2) {
    combine(cur); 
  }
}

long long num_tours() {
  return dp[1].rep; 
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14