QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#548700#6404. Shuttle Tourpandapythoner#WA 75ms3648kbC++234.7kb2024-09-05 20:15:282024-09-05 20:15:29

Judging History

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

  • [2024-09-05 20:15:29]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:3648kb
  • [2024-09-05 20:15:28]
  • 提交

answer

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

using ll = long long;
using ld = long double;

#define len(a) int((a).size())
#define all(a) begin(a), end(a)
#define rep(i, n) for (int i = 0; i < (n); i++)

struct SGT {
    int n;
    vector<array<ll, 50>> mx;
    vector<array<ll, 50>> mn;


    void upd(int v) {
        if (mx[v + v][0] == -1) {
            mx[v] = mx[v + v + 1];
            mn[v] = mn[v + v + 1];
        } else if (mx[v + v + 1][0] == -1) {
            mx[v] = mx[v + v];
            mn[v] = mn[v + v];
        } else {
            rep(i, 50) {
                mx[v][i] = max(mx[v + v][i], mx[v + v + 1][i]);
                mn[v][i] = min(mn[v + v][i], mn[v + v + 1][i]);
            }
        }
    }

    void build(vector<array<ll, 50>> a) {
        n = 1;
        while (n < len(a)) n *= 2;
        mx.resize(n * 2);
        mn.resize(n * 2);
        for (int i = 0; i < len(a); i += 1) {
            mx[i + n] = a[i];
            mn[i + n] = a[i];
        }
        for (int i = n - 1; i >= 1; i -= 1) upd(i);
    }


    void set(int i, array<ll, 50> x) {
        i += n;
        mx[i] = mn[i] = x;
        for (i /= 2; i >= 1; i /= 2) upd(i);
    }


    ll get(int l, int r) {
        l += n;
        r += n + 1;
        array<ll, 50> rmn, rmx;
        rmn.fill(-1);
        rmx.fill(-1);
        while (l < r) {
            if (l & 1) {
                if (rmn[0] == -1) {
                    rmn = mn[l];
                    rmx = mx[l];
                } else if (mn[l][0] != -1) {
                    rep(i, 50) {
                        rmn[i] = min(rmn[i], mn[l][i]);
                        rmx[i] = max(rmx[i], mx[l][i]);
                    }
                }
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                if (rmn[0] == -1) {
                    rmn = mn[r];
                    rmx = mx[r];
                } else if (mn[r][0] != -1) {
                    rep(i, 50) {
                        rmn[i] = min(rmn[i], mn[r][i]);
                        rmx[i] = max(rmx[i], mx[r][i]);
                    }
                }
            }
            l /= 2;
            r /= 2;
        }
        if (rmn[0] == -1) {
            return -1;
        }
        ll rs = 0;
        rep(i, 50) rs += rmx[i] - rmn[i];
        rs *= 2;
        return rs;
    }
};

struct edge {
    int to;
    ll w;
};


int n, q;
vector<int> status;
vector<vector<edge>> g;
vector<ll> depth, dir;
int cur_way;
vector<int> my_way;
array<ll, 50> start;
vector<array<ll, 50>> values, to_build;
SGT sgt;


array<ll, 50> get(int i) {
    if (status[i] == 0) {
        array<ll, 50> rs;
        rs.fill(-1);
        return rs;
    }
    return values[i];
}

void dfs1(int v, int p, int way) {
    my_way[v] = way;
    depth[v] = 0;
    int last_way = way;
    rep(i, len(g[v])) {
        auto [to, w] = g[v][i];
        if (to == p) continue;
        if (last_way == -1) {
            last_way = cur_way++;
            dir[to] = -1;
            dfs1(to, v, last_way);
            start[last_way] = depth[to] + w;
        } else {
            dir[to] = 1;
            dfs1(to, v, last_way);
            last_way = -1;
        }
        if (to == g[v][0].to) depth[v] = depth[to] + w;;
    }
}


void dfs2(int v, int p, array<ll, 50> cur) {
    values[v] = cur;
    for (auto [to, w] : g[v]) {
        if (to == p) continue;
        auto new_cur = cur;
        new_cur[my_way[to]] += w * dir[to];
        dfs2(to, v, new_cur);
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    status.resize(n);
    rep(i, n) {
        char c;
        cin >> c;
        status[i] = c - '0';
    }
    g.assign(n, vector<edge>());
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        ll w;
        cin >> w;
        --u;
        --v;
        g[u].push_back(edge{ v, w });
        g[v].push_back(edge{ u, w });
    }
    cur_way = 0;
    depth.resize(n);
    my_way.resize(n);
    dir.resize(n);
    start.fill(0);
    dfs1(0, -1, cur_way++);
    assert(cur_way <= 50);
    values.resize(n);
    dfs2(0, -1, start);
    to_build.resize(n);
    rep(i, n) to_build[i] = get(i);
    sgt.build(to_build);
    rep(itr, q) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            cin >> i; --i;
            status[i] ^= 1;
            sgt.set(i, get(i));
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            --r;
            cout << sgt.get(l, r) << "\n";
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3504kb

input:

5 6
10110
1 2 1
1 3 10
2 4 100
3 5 1000
2 1 5
1 3
2 1 5
2 2 4
2 5 5
2 1 1

output:

222
202
0
-1
0

result:

ok 5 number(s): "222 202 0 -1 0"

Test #2:

score: -100
Wrong Answer
time: 75ms
memory: 3648kb

input:

50 200000
00100100100001101010110100000111100011101110011010
14 47 940241413
11 43 331483591
37 38 496247070
47 46 832459694
7 15 16479291
1 30 402388666
30 8 513064064
46 50 739311480
5 4 761894947
32 41 631669659
17 24 715786564
35 20 763151642
32 33 492466005
39 11 186023146
9 7 805081251
3 42 25...

output:

14791979216
-1
20715738612
23325988182
17069597570
20715738612
9502580630
15941798978
18021369606
17611105778
24834126796
6376951784
9380710234
19555194264
13472642612
2856655228
13265613728
0
-1
7423162186
23006121528
20509245732
21668931298
17126179898
7974594860
7695830712
15500543778
0
244257220...

result:

wrong answer 1st numbers differ - expected: '17149847378', found: '14791979216'