Submission #1007759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007759		Namkhing	JOI tour (JOI24_joitour)	C++17	0 / 100	126 ms	34860 KiB

joitour

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

ll n, q;
vector<ll> f, dp, order;
vector<vector<ll>> adj, cou;

void dfs(int u, int p) {
    for (ll& v : adj[u]) {
        if (v == p) {
            swap(v, adj[u].back());
            adj[u].pop_back();
            break;
        }
    }
    
    for (int v : adj[u]) {
        dfs(v, u);
    }
    
    order.push_back(u);
}

void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
    n = N, q = Q;
    f.resize(N);
    dp.resize(N);
    cou.resize(3, vector<ll>(N));
    adj.resize(N);

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

    for (int j = 0; j < N - 1; j++) {
        adj[U[j]].push_back(V[j]);
        adj[V[j]].push_back(U[j]);
    }

    dfs(0, -1);
}

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

long long num_tours() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cou[j][i] = 0;
        }
        dp[i] = 0;
    }
    
    for (int u : order) {
        cou[f[u]][u] = 1;
        
        for (int v : adj[u]) {
            for (int i = 0; i < 3; i++) {
                cou[i][u] += cou[i][v];
            }
        }
    }

    ll sum = 0;
    
    for (int u : order) {
        if (f[u] == 1) {
            for (int v : adj[u]) {
                sum += cou[0][v] * cou[2][v];
            }
            
            dp[u] = cou[0][u] * cou[2][u] - sum;
            dp[u] += cou[0][u] * (cou[2][0] - cou[2][u]);
            dp[u] += cou[2][u] * (cou[0][0] - cou[0][u]);
        }

        for (int v : adj[u]) {
            dp[u] += dp[v];
        }
    }
    
    return dp[0];
}

• 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