Submission #1194970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194970		vjudge2	JOI tour (JOI24_joitour)	C++20	20 / 100	3097 ms	34076 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];

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]);
    }            // for (auto& v : adj[i]) if (v != par[i]) ans -= cnt[v][0] * cnt[v][2];

    par[0] = -1;
    for (int i = 0; i < N; i++) f[i] = F[i];
}

void change(i32 X, i32 Y) {
    f[X] = Y;
}

int num_tours() {
    dfs(0, -1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (f[i] == 1) {
            ans += (cnt[0][0] - cnt[i][0]) * (cnt[i][2]);
            // cout << "ans: " << ans << '\n';
            ans += (cnt[0][2] - cnt[i][2]) * (cnt[i][0]);
                        // cout << ans << '\n';


            ans += (cnt[i][0] * cnt[i][2]);
            // cout << ans << '\n';

            for (auto& v : adj[i]) if (v != par[i]) ans -= cnt[v][0] * cnt[v][2];
        }
        // cout << f[i] << " ";
    }
    // cout << '\n';
    return ans;
}
            // for (auto& v : adj[i]) if (v != par[i]) ans -= cnt[v][0] * cnt[v][2];

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