QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810523#8647. JOI Tourtopfloorboss0 4ms4712kbC++2011.0kb2024-12-12 00:25:462024-12-12 00:25:52

Judging History

你现在查看的是最新测评结果

  • [2024-12-12 00:25:52]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:4712kb
  • [2024-12-12 00:25:46]
  • 提交

answer

#include "joitour.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>

using namespace std;

struct Fenwick {
    int n;
    vector<long long> tree;

    Fenwick() {}

    void build(int x) {
        n = x;
        tree.resize(n + 1);
    }

    long long get_sum(int ind){
        long long ans = 0;
        for (int i = ind; i >= 0; i = (i & (i + 1)) - 1){
            ans += tree[i];
        }
        return ans;
    }

    void upd(int ind, long long x){
        for (int i = ind; i < n; i = (i | (i + 1))){
            tree[i] += x;
        }
    }

    long long su(int l, int r){
        return get_sum(r) - get_sum(l-1);
    }
};

struct Fenwick2 {
    int n;
    vector<long long> tree;

    Fenwick2() {}

    void build(int x) {
        n = x;
        tree.resize(n + 3);
    }

    long long get(int ind) {
        long long ans = 0;
        for (int i = ind; i >= 0; i = (i & (i + 1)) - 1){
            ans += tree[i];
        }
        return ans;
    }

    void upd(int ind, long long x) {
        for (int i = ind; i < n; i = (i | (i + 1))){
            tree[i] += x;
        }
    }

    void upd(int l, int r, int x) {
        upd(l, x);
        upd(r + 1, -x);
    }
};
vector<vector<int>> g;
vector<int> col;

long long anss = 0;

struct HLD {
    vector<vector<int>> gr;
    map<int, int> gt;
    vector<int> ord, tin, tout, backord, up, sz, pr, uppest, c;
    vector<long long> ct01, ct21, ct0, ct2;
    vector<Fenwick> lol;
    Fenwick2 lol1;
    int timer = 1;
    long long ans = 0, tans = 0;

    void dfssz(int v, int p) {
        if (p != -1) {
            pr[v] = p;
            for (int i = 0; i < (int)gr[v].size() - 1; ++i) {
                if (gr[v][i] == p) {
                    swap(gr[v][i], gr[v][i + 1]);
                }
            }
            if (gr[v].size()) gr[v].pop_back();
        }
        if (p == -1) {
            for (auto e : gr[v]) {
                uppest[e] = e;
            }
        } else {
            for (auto e : gr[v]) {
                uppest[e] = uppest[v];
            }
        }
        sz[v] = 1;
        tin[v] = timer++;
        for (auto e : gr[v]) {
            dfssz(e, v);
            ct0[v] += ct0[e];
            ct2[v] += ct2[e];
            ct01[v] += ct01[e];
            ct21[v] += ct21[e];
            sz[v] += sz[e];
        }
        tout[v] = timer++;
        if (c[v] == 0) {
            ct0[v]++;
        }
        if (c[v] == 2) {
            ct2[v]++;
        }
        if (c[v] == 1) {
            ct01[v] += ct0[v];
            ct21[v] += ct2[v];
        }
    }

    void dfs(int v) {
        backord[v] = ord.size();
        ord.push_back(v);
        if (gr[v].size() == 0) return;
        for (auto &e : gr[v]) {
            up[e] = e;
            if (sz[e] > sz[gr[v][0]]) {
                swap(e, gr[v][0]);
            }
        }
        up[gr[v][0]] = up[v];
        for (auto e : gr[v]) {
            dfs(e);
        }
    }

    HLD(){}

    void upd(int v, int x) {
        lol1.upd(backord[v], backord[v] + sz[v] - 1, x);
    }

    long long get1s(int v) {
        return lol1.get(backord[v]);
    }

    long long get0s(int v) {
        return lol[0].su(backord[v], backord[v] + sz[v] - 1);
    }

    long long get2s(int v) {
        return lol[2].su(backord[v], backord[v] + sz[v] - 1);
    }

    void build(vector<int> kek) {
        int n = (int)kek.size();
        gr.resize(n);
        for (int i = 0; i < n; ++i) gt[kek[i]] = i;
        c.resize(n);
        for (int i = 0; i < n; ++i) {
            c[i] = col[kek[i]];
            for (auto e : g[kek[i]]) {
                if (gt.find(e) != gt.end()) {
                    gr[i].push_back(gt[e]);
                }
            }
        }
        uppest.resize(n);
        tin.resize(n);
        tout.resize(n);
        backord.resize(n);
        up.resize(n);
        sz.resize(n);
        pr.resize(n);
        ct0.resize(n);
        ct2.resize(n);
        ct01.resize(n);
        ct21.resize(n);
        dfssz(0, -1);
        dfs(0);
        lol.resize(3);
        lol1.build(n);
        for (int i = 0; i < 3; ++i) {
            if (i == 1) continue;
            lol[i].build(n);
        }
        for (int i = 0; i < n; ++i) {
            if (c[ord[i]] == 1) continue;
            lol[c[ord[i]]].upd(i, 1);
        }
        for (int i = 0; i < n; ++i) {
            if (c[ord[i]] == 1) {
                upd(ord[i], 1);
            }
        }
        for (auto e : gr[0]) {
            ans += ct01[e] * (ct2[0] - ct2[e]);
            ans += ct21[e] * (ct0[0] - ct0[e]);
            int T = ct2[0] - ct2[e];
            if (c[0] == 2) T--;
            if (c[0] == 1) {
                ans += ct0[e] * (ct2[0] - ct2[e]);
            }
            // tans += ct0[e] * T;
        }
    }

    int get01(int v) {
        if (c[0] == 1) return ct01[0] - ct01[v] - ct0[0];
        return ct01[0] - ct01[v];
    }

    int get21(int v) {
        if (c[0] == 1) return ct21[0] - ct21[v] - ct2[0];
        return ct21[0] - ct21[v];
    }

    void kek1(int v, int col) {
        v = gt[v];
        if (v == 0) {
            if (c[v] == 2) {
                ans -= ct01[0];
                ct2[v]--;
                lol[2].upd(backord[v], -1);
            }
            if (c[v] == 0) {
                ans -= ct21[0];
                ct0[v]--;
                lol[0].upd(backord[v], -1);
            }
            if (c[v] == 1) {
                ct01[v] -= ct0[v];
                ct21[v] -= ct2[v];
                upd(0, -1);
            }
            c[v] = col;
            if (c[v] == 2) {
                ans += ct01[0];
                ct2[v]++;
                lol[2].upd(backord[v], 1);
            }
            if (c[v] == 0) {
                ans += ct21[0];
                ct0[v]++;
                lol[0].upd(backord[v], 1);
            }
            if (c[v] == 1) {
                ct01[v] += ct0[v];
                ct21[v] += ct2[v];
                upd(0, 1);
            }
            return;
        }
        int t = uppest[v];
        int e = t;
        if (c[v] == 0) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans -= TT * (ct2[0] - ct2[t]);
            ans -= get21(t);
            ct0[t]--;
            ct01[t] -= get1s(v);
            if (c[0] == 1) ct01[t]++;
            ct0[0]--;
            ct01[0] -= get1s(v);
            lol[0].upd(backord[v], -1);
            int T = ct2[0] - ct2[t];
            if (c[0] == 2) T--;
            tans -= T;
        }
        if (c[v] == 1) {
            ans -= get0s(v) * (ct2[0] - ct2[t]);
            ans -= get2s(v) * (ct0[0] - ct0[t]);
            ct01[0] -= get0s(v);
            ct21[0] -= get2s(v);
            upd(v, -1);
        }
        if (c[v] == 2) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans -= TT * (ct0[0] - ct0[t]);
            ans -= get01(t);
            // cout << get01(t) << ' ' << get1s(v) * (ct0[0] - ct0[t]) << ' ' << ans << ' ';
            ct2[t]--;
            ct21[t] -= get1s(v);
            if (c[0] == 1) ct21[t]++;
            ct2[0]--;
            ct21[0] -= get1s(v);
            lol[2].upd(backord[v], -1);
            int T = ct0[0] - ct0[t];
            if (c[0] == 0) T--;
            tans -= T;
        }
        c[v] = col;
        if (c[v] == 0) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans += TT * (ct2[0] - ct2[t]);
            ans += get21(t);
            ct0[t]++;
            ct01[t] += get1s(v);
            if (c[0] == 1) ct01[t]--;
            ct0[0]++;
            ct01[0] += get1s(v);
            lol[0].upd(backord[v], 1);
            int T = ct2[0] - ct2[t];
            if (c[0] == 2) T--;
            tans += T;
        }
        if (c[v] == 1) {
            ans += get0s(v) * (ct2[0] - ct2[t]);
            ans += get2s(v) * (ct0[0] - ct0[t]);
            ct01[0] += get0s(v);
            ct21[0] += get2s(v);
            upd(v, 1);
        }
        if (c[v] == 2) {
            int TT = get1s(v);
            if (c[0] == 1) TT--;
            ans += TT * (ct0[0] - ct0[t]);
            ans += get01(t);
            ct2[t]++;
            ct21[t] += get1s(v);
            if (c[0] == 1) ct21[t]--;
            ct2[0]++;
            ct21[0] += get1s(v);
            lol[2].upd(backord[v], 1);
            int T = ct0[0] - ct0[t];
            if (c[0] == 0) T--;
            tans += T;
        }
        e = t;
    }

    long long getans() {
        if (c[0] == 1) return ans + tans;
        return ans;
    }
};

vector<HLD> lol;
vector<int> sz, cc, ord;
vector<vector<int>> p;

void dfssz(int v, int pr) {
    sz[v] = 1;
    for (auto e : g[v]) {
        if (e == pr) continue;
        if (cc[e] != -1) continue;
        dfssz(e, v);
        sz[v] += sz[e];
    }
    ord.push_back(v);
}

void find_centroid(int v, int d) {
    ord.clear();
    dfssz(v, -1);
    int N = sz[v];
    int cntr = -1;
    for (auto &e : ord) {
        if (sz[e] > N / 2) {
            cntr = e;
            swap(e, ord[0]);
            break;
        }
    }
    lol[cntr].build(ord);
    cc[cntr] = d;
    for (auto e : ord) {
        p[d][e] = cntr;
    }
    for (auto e : g[cntr]) {
        if (cc[e] == -1) {
            find_centroid(e, d + 1);
        }
    }
}

void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q) {
    g.resize(N);
    sz.resize(N);
    p.resize(20, vector<int>(N));
    cc.resize(N, -1);
    col = F;
    for (int i = 0; i < N - 1; ++i) {
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
    }
    lol.resize(N);
    find_centroid(0, 0);
    for (auto e : lol) anss += e.getans();
}

void change(int X, int Y) {
    for (int i = 0; i <= cc[X]; ++i) {
        anss -= lol[p[i][X]].getans();
        lol[p[i][X]].kek1(X, Y);
        anss += lol[p[i][X]].getans();
    }
}

long long num_tours() {
    return anss;
}

#ifdef LOCAL 

int main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  int N;
  assert(scanf("%d", &N) == 1);

  std::vector<int> F(N);
  for (int i = 0; i < N; i++) {
    assert(scanf("%d", &F[i]) == 1);
  }

  std::vector<int> U(N - 1), V(N - 1);
  for (int j = 0; j < N - 1; j++) {
    assert(scanf("%d %d", &U[j], &V[j]) == 2);
  }

  int Q;
  assert(scanf("%d", &Q) == 1);

  init(N, F, U, V, Q);
  printf("%lld\n", num_tours());
  fflush(stdout);

  for (int k = 0; k < Q; k++) {
    int X, Y;
    assert(scanf("%d %d", &X, &Y) == 2);

    change(X, Y);
    printf("%lld\n", num_tours());
    fflush(stdout);
  }
}


#endif

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 4712kb

input:

400
1 1 0 2 2 0 2 1 1 1 1 0 1 2 2 2 2 0 0 2 0 2 0 2 1 1 2 2 1 2 1 0 1 2 2 2 0 0 0 2 1 2 2 0 0 0 1 2 1 1 0 1 1 2 1 2 2 2 1 1 0 1 1 1 2 2 1 1 0 0 1 1 0 0 1 1 1 2 2 2 1 1 2 1 1 1 0 2 0 2 1 0 1 1 2 0 0 2 1 0 2 2 1 0 0 0 0 1 1 1 0 1 2 1 1 1 2 0 2 2 0 2 0 1 0 1 1 1 1 0 1 1 0 0 0 2 2 0 2 2 2 1 1 0 1 2 0 1 ...

output:

597892
604438
604222
600458
598015
594436
593625
586019
582403
581750
586857
587940
591404
592133
589209
587741
591739
595777
591792
591577
593683
592092
587464
583167
582283
580846
576415
577726
579563
578399
577998
577041
577680
584022
591611
594461
591140
590147
583481
582592
581026
585738
587414...

result:

wrong answer 

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

input:

200000
0 2 2 0 2 2 0 1 1 0 2 2 0 1 2 2 0 1 0 2 1 1 0 1 0 2 0 2 0 0 0 1 0 0 2 0 2 1 0 0 1 1 1 0 0 2 1 2 2 1 0 2 2 2 0 2 2 1 2 0 1 0 0 1 2 0 0 2 1 1 1 0 1 1 1 2 1 0 1 1 0 1 2 2 2 0 1 0 1 1 0 2 0 1 0 2 0 0 2 2 2 2 2 0 0 2 1 2 2 1 2 0 1 1 1 1 1 0 2 0 2 0 1 1 1 0 1 0 2 1 2 0 1 1 0 2 1 2 2 2 0 0 2 2 2 0 1...

output:

77241161705660

result:


Subtask #4:

score: 0
Wrong Answer

Test #38:

score: 16
Accepted
time: 1ms
memory: 3788kb

input:

3
1 1 1
0 1
1 2
100
2 0
0 0
0 2
2 1
0 1
0 0
0 1
0 0
1 0
2 2
0 1
0 0
0 1
1 1
0 0
2 0
2 1
2 2
0 2
2 1
2 2
2 0
0 1
2 1
0 2
0 1
2 0
2 1
0 0
2 0
2 1
2 2
0 2
2 0
0 0
2 1
2 0
2 2
1 2
0 1
1 1
2 1
0 0
0 2
0 1
0 0
1 2
1 0
1 2
1 0
0 1
2 2
2 1
2 2
0 2
1 2
2 1
0 0
0 2
0 1
1 1
2 0
0 0
1 2
0 2
0 0
1 0
0 1
0 2
2 1
...

output:

0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0

result:

ok 

Test #39:

score: 0
Wrong Answer
time: 1ms
memory: 3788kb

input:

4
2 2 2 0
0 1
1 2
2 3
100
0 0
3 2
1 1
3 1
0 2
2 0
1 0
3 0
0 1
1 2
0 0
3 2
3 1
1 0
3 2
3 0
3 1
1 2
3 2
0 1
2 2
2 1
1 0
1 1
1 0
3 0
0 2
1 2
0 0
3 1
1 0
2 0
3 0
2 2
3 2
0 2
0 1
3 1
2 1
3 0
1 2
2 2
3 2
2 1
1 1
3 1
1 2
2 0
0 2
1 1
0 1
3 0
2 2
0 2
0 0
1 0
3 1
2 1
0 2
2 2
0 0
0 1
3 0
2 1
1 2
3 1
3 2
1 1
2 ...

output:

0
0
0
1
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
-1
1
1
2
3
2
0
0
1
2
1
0
0
0
0
0
1
2
0
-2
-1
-2
-1
0
2
2
2
1
3
0
1
1
1
-1
0
0
-1
-1
-1
1
2
3
0
0
-1
0
-1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
2
2
2
1
1
1
0
0
0
1
1
2
1

result:

wrong answer 

Subtask #5:

score: 0
Wrong Answer

Test #60:

score: 16
Accepted
time: 1ms
memory: 3900kb

input:

3
2 0 0
0 1
0 2
100
0 1
2 2
2 1
1 1
0 0
2 2
1 2
0 2
0 1
0 0
0 1
0 2
2 1
1 0
2 2
2 0
0 0
0 2
1 1
1 2
2 2
2 1
0 0
2 2
0 1
1 0
0 0
2 0
1 1
1 0
2 1
2 0
0 2
0 1
2 2
1 1
0 0
0 1
2 1
0 0
2 0
0 1
2 1
2 0
0 2
2 2
0 1
2 0
0 0
0 1
2 1
0 2
0 1
0 2
2 2
1 0
1 1
1 2
1 0
1 2
1 0
0 0
1 1
0 1
1 0
2 0
1 2
1 0
0 2
0 0
...

output:

0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 

Test #61:

score: 0
Wrong Answer
time: 1ms
memory: 3820kb

input:

4
1 0 1 0
0 1
0 2
1 3
100
0 2
3 2
1 1
0 1
3 1
3 2
3 1
2 2
1 2
2 1
1 0
2 2
3 2
3 1
1 1
3 2
2 0
3 1
0 2
1 2
2 1
2 2
0 1
1 0
3 0
3 2
3 1
3 0
0 0
2 0
1 1
1 2
0 1
1 0
2 2
2 1
1 1
3 2
0 0
2 2
0 1
3 1
1 0
2 1
2 0
1 2
0 2
3 0
3 1
0 1
0 2
3 2
3 1
1 1
1 0
2 2
0 0
0 1
0 0
0 1
0 0
2 0
0 1
3 2
0 2
3 0
2 2
2 1
3 ...

output:

0
0
0
0
0
0
0
0
0
0
0
1
2
2
2
0
0
2
0
0
0
0
0
0
2
4
2
2
4
2
2
1
1
2
2
4
2
1
1
2
2
1
0
2
1
1
2
1
2
1
2
1
2
1
0
1
1
1
2
1
2
1
1
1
3
2
2
2
2
2
2
2
2
2
4
3
2
2
2
2
2
2
2
2
2
2
2
2
1
0
1
1
2
2
2
2
2
1
1
1
1

result:

wrong answer 

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%