제출 #1194990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194990		vjudge2	JOI tour (JOI24_joitour)	C++20	6 / 100	89 ms	36396 KiB

joitour

#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;

using i32 = int32_t;
#define int long long

const int maxn = 2e5 + 5;
vector<int> adj[maxn];
int n, f[maxn], cnt[maxn][3], par[maxn], c0, c2, sc0, sc2, sum;

void dfs(int u, int p = -1) {
    for (int i = 0; i < 3; i++) cnt[u][i] = 0;
    cnt[u][f[u]] = 1;
    for (auto& v : adj[u]) {
        if (v == p) continue;
        par[v] = u;
        dfs(v, u);
        for (int i = 0; i < 3; i++) {
            cnt[u][i] += cnt[v][i];
        }
    }
}

void init(i32 N, std::vector<i32> F, std::vector<i32> U, std::vector<i32> V,
          i32 Q) {
    n = N;
    for (int i = 0; i < N - 1; i++) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }            
    par[0] = -1;
    for (int i = 0; i < N; i++) f[i] = F[i], c0 += (f[i] == 0), c2 += (f[i] == 2);
    dfs(0, -1);
    for (int i = 0; i < n; i++) {
        if (f[i] == 1) {
            int u = i;
            sc0 += cnt[u][0];
            sc2 += cnt[u][2];
            sum -= cnt[u][0] * cnt[u][2];
            for (auto& v : adj[u]) if (v != par[u]) sum -= cnt[v][0] * cnt[v][2];
        }
    }
}

void change(i32 X, i32 Y) {
    c0 -= (f[X] == 0);
    c2 -= (f[X] == 2);
    int u = X;
    if (f[X] == 1) {
        sc0 -= cnt[u][0];
        sc2 -= cnt[u][2];
        sum += cnt[u][0] * cnt[u][2];
        for (auto& v : adj[u]) if (v != par[u]) sum += cnt[v][0] * cnt[v][2];
    }
    cnt[u][f[X]] -= 1;
    cnt[u][Y] += 1;
    if (Y == 1) {
        sc0 += cnt[u][0];
        sc2 += cnt[u][2];
        sum -= cnt[u][0] * cnt[u][2];
        for (auto& v : adj[u]) if (v != par[u]) sum -= cnt[v][0] * cnt[v][2];
    }
    while (par[u] != -1) {
        u = par[u];
        if (f[u] == 1) {
            sc0 -= cnt[u][0];
            sc2 -= cnt[u][2];
            sum += cnt[u][0] * cnt[u][2];
            for (auto& v : adj[u]) if (v != par[u]) sum += cnt[v][0] * cnt[v][2];
        }
        cnt[u][f[X]] -= 1;
        cnt[u][Y] += 1;
        if (f[u] == 1) {
            sc0 += cnt[u][0];
            sc2 += cnt[u][2];
            sum -= cnt[u][0] * cnt[u][2];
            for (auto& v : adj[u]) if (v != par[u]) sum -= cnt[v][0] * cnt[v][2];
        }
    }
    f[X] = Y;
    c0 += (f[X] == 0);
    c2 += (f[X] == 2);
}

int num_tours() {
    int ans = 0;
    return c0 * sc2 + c2 * sc0 + sum;
}

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