Submission #1091533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091533		thangdz2k7	JOI tour (JOI24_joitour)	C++17	0 / 100	468 ms	44540 KiB

joitour

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int MaxN = 2e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, par[MaxN], sz[MaxN];
vi badj[MaxN], f;

int dfs(int u, int p = -1){
    sz[u] = 1;
    for (int v : badj[u]) if (v != p && par[v] < -1) sz[u] += dfs(v, u);
    return sz[u];
}

int get_cen(int u, int m, int p = -1){
    for (int v : badj[u]) if (v != p && par[v] < -1 && sz[v] * 2 > m) return get_cen(v, m, u);
    return u;
}

int root;

void cen(int u = 0, int p = -1){
    u = get_cen(u, dfs(u)); par[u] = p; if (p == -1) root = u;
    for (int v : badj[u]) if (par[v] < -1) cen(v, u);
}

vector <ii> pairs = {{6, 1}, {4, 3}, {4, 2}, {4, 1}, {2, 1}};
ll cnt[MaxN][8]; int sign[MaxN][8];

void rs(int u, int child, int val){ if (u == -1) return;
    if (val < 0) if (par[u] != -1) rs(par[u], u, val);
    if (val < 0) for (int i = 0; i < 8; ++ i) cnt[u][i] -= cnt[child][i];
    for (auto [l, r] : pairs) cnt[u][l | r] += val * (cnt[u][l] * cnt[child][r] + cnt[child][l] * cnt[u][r]);
    if (val > 0) for (int i = 0; i < 8; ++ i) cnt[u][i] += cnt[child][i];
    if (val > 0) if (par[u] != -1) rs(par[u], u, val);
}

void add(int u, int t, int val){ t = 1 << t;
    rs(par[u], u, -1); //if (val == -1) return;
    for (auto [l, r] : pairs) if (r == t || l == t) cnt[u][l | r] -= sign[u][t] * cnt[u][l ^ r ^ t];
    if (t == 2) cnt[u][7] -= sign[u][t] * cnt[u][5];
    cnt[u][t] += val; if (val == 1) sign[u][t] = 1; else sign[u][t] = 0;
    for (auto [l, r] : pairs) if (r == t || l == t) cnt[u][l | r] += sign[u][t] * cnt[u][l ^ r ^ t];
    if (t == 2) cnt[u][7] += sign[u][t] * cnt[u][5]; rs(par[u], u, 1);
}

void init(int N, vi F, vi U, vi V, int Q){
    for (int i = 0; i < N - 1; ++ i){
        int u = U[i], v = V[i];
        badj[u].pb(v); badj[v].pb(u);
    }
    for (int i = 0; i < N; ++ i) par[i] = -2; cen(); f = F;
    //for (int i = 0; i < N; ++ i) cerr << i << ' ' << par[i] << endl;
    for (int i = 0; i < N; ++ i) add(i, f[i], 1);
    //add(0, f[0], 1);
    //add(2, f[2], -1);
    //for (int i = 0; i < N; ++ i){
        //for (int j = 0; j < 8; ++ j) cout << cnt[i][j] << ' ';
        //cout << endl;
    //}
}

void change(int u, int t){
    add(u, f[u], -1);
    f[u] = t; add(u, f[u], 1);
}

ll num_tours(){ return cnt[root][7];}

Compilation message (stderr)

joitour.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
joitour.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
joitour.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
joitour.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
joitour.cpp: In function 'void add(int, int, int)':
joitour.cpp:59:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |     if (t == 2) cnt[u][7] += sign[u][t] * cnt[u][5]; rs(par[u], u, 1);
      |     ^~
joitour.cpp:59:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |     if (t == 2) cnt[u][7] += sign[u][t] * cnt[u][5]; rs(par[u], u, 1);
      |                                                      ^~
joitour.cpp: In function 'void init(int, vi, vi, vi, int)':
joitour.cpp:67:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   67 |     for (int i = 0; i < N; ++ i) par[i] = -2; cen(); f = F;
      |     ^~~
joitour.cpp:67:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   67 |     for (int i = 0; i < N; ++ i) par[i] = -2; cen(); f = F;
      |                                               ^~~

• 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