QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#646357#6404. Shuttle Tourcrimsonsunset#RE 0ms3700kbC++2011.0kb2024-10-16 22:23:132024-10-16 22:23:14

Judging History

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

  • [2024-10-16 22:23:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3700kb
  • [2024-10-16 22:23:13]
  • 提交

answer

#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;

#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long long ll;
typedef long double ld;

struct Node {
    int mx = 0, mn = 1e16;
};

struct SegmentTree {
    vector<int> lol;
    vector<Node> tr;
    int sz;

    SegmentTree() {};

    void build(vector<int> lollol) {
        lol = lollol;
        sort(all(lol));
        lol.push_back(3e5);
        int n = lol.size();
        sz = (1ll<<(int)(log2(n)))*2;
        tr.resize(2*sz);
    };

    Node merge(Node a, Node b) {
        Node c = {max(a.mx, b.mx), min(a.mn, b.mn)};
        return c;
    }

    void update(int v, int l, int r, int ind, int x) {
        if(l > ind || r <= ind) return;
        if(r - l == 1) {
            tr[v].mn = x;
            tr[v].mx = x;
            if (x == -1) {
                tr[v].mx = 0;
                tr[v].mn = 1e16;
            }
            return;
        }
        int m = (l + r) / 2;
        update(2 * v + 1, l, m, ind, x);
        update(2 * v + 2, m, r, ind, x);
        tr[v] = merge(tr[2 * v + 1], tr[2 * v + 2]);
        // cout << "mnmx" << tr[v].mn << ' ' << tr[v].mx << '\n';
    };

    void update(int ind, int x) {
        ind = (lower_bound(all(lol), ind) - lol.begin());
        // cout << "XXX" << ind << '\n';
        update(0, 0, sz, ind, x);
    };

    Node get(int v, int l, int r, int ql, int qr) {
        if(ql <= l && qr >= r) {
            return tr[v];
        }
        if(l >= qr || r <= ql) return {0, (int)1e16};
        int m = (l + r) / 2;
        return merge(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
    };

    Node get(int ql, int qr) {
        // return tr[0];
        // cout << ql << ' ' << qr << endl;
        // for (auto e : lol) cout << e << ' '; cout << endl;
        ql = lower_bound(all(lol), ql) - lol.begin();
        qr = lower_bound(all(lol), qr) - lol.begin();
        // cout << ql << ' ' << qr << endl;
        if (ql == qr) return {0, (int)1e16};
        return get(0, 0, sz, ql, qr);
    }
};


vector<int> fuckfuck;
vector<vector<pair<int, int>>> gr;
vector<int> lol;
map<int, vector<int>> backlol;
vector<map<int, int>> lol2;
vector<int> h, pr, tin, tout;
int dd[(int)2e5];
int timer = 1;

void dfs(int v, int p) {
    tin[v] = timer; timer++;
    pr[v] = p;
    for (auto e : gr[v]) {
        if (e.first == p) continue;
        h[e.first] = h[v] + e.second;
        dd[e.first] = dd[v] + 1;
        dfs(e.first, v);
        fuckfuck[lol[e.first]] += e.second;
        lol[v] = lol[e.first];
    }
    if (gr[v].size() == 1 && pr[v] != -1) lol[v] = v;
    backlol[lol[v]].push_back(v);
    tout[v] = timer; timer++;
    lol2[lol[v]][h[v]] = v;
}

map<pair<int, int>, int> d;
vector<int> lolkek;

int D(int i, int j) {
    if (i == j) return 0;
    if (h[i] > h[j]) swap(i, j);
    if (tin[i] < tin[j] && tout[i] > tout[j]) return h[j] - h[i];
    return h[i] + h[j] - 2 * d[{lolkek[lol[i]], lolkek[lol[j]]}];
}

vector<int> comp[(int)2e5];


struct sparse_table {
    vector<vector<pair<int, int>>> d;
    sparse_table() {}

    void build(vector<pair<int, int>> a) {
        int n = a.size();
        d.resize(__lg(n) + 1, a);
        for (int i = 1; i <= __lg(n); ++i)
            for (int j = 0; j + (1 << (i - 1)) < n; ++j)
                d[i][j] = min(d[i - 1][j], d[i - 1][j + (1 << (i - 1))]);
    }

    int get(int l, int r) {
        if (l > r)
            return 0;
        ++r;
        int t = __lg(r - l);
        return min(d[t][l], d[t][r - (1 << t)]).second;
    }
} sp;

int getLCA(int u, int v) {
    return sp.get(u, v);
}

int dist(vector<int> a) {
    vector<pair<int, int>> vert;
    for (int i : a)
        vert.emplace_back(tin[i], i);
    sort(vert.begin(), vert.end());
    int root = vert[0].second;
    for (int i = 1; i < (int)vert.size(); i++) root = getLCA(root, vert[i].second);

    int ans = 1;
    stack<int> st;
    st.push(root);
    vector<int> allV = {root};

    for (auto [tt, v] : vert) {
        int lastV = -1;
        if (v == st.top()) continue;
        int u = getLCA(st.top(), v);
        while (!st.empty() && h[st.top()] > h[u]) {
            lastV = st.top();
            st.pop();
        }
        if (st.top() == u) {
            comp[st.top()].push_back(v);
        } else {
            if (lastV == -1) assert(0);
            if (comp[st.top()].empty() || comp[st.top()].back() != lastV) assert(0);
            comp[st.top()].pop_back();
            comp[st.top()].push_back(u);
            comp[u].push_back(lastV);
            comp[u].push_back(v);
            st.push(u);
            allV.push_back(u);
        }
        st.push(v);
        allV.push_back(v);
    }

    for (int v : allV) {
        for (int u : comp[v]) {
            ans += h[u] - h[v];
        }
    }
    for (int v : allV) {
        comp[v].clear();
        comp[v].shrink_to_fit();
    }
    return ans;
}


void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int sum = 0;
    fuckfuck.resize(n);
    gr.resize(n); lol.resize(n); h.resize(n); pr.resize(n); tin.resize(n); tout.resize(n); lol2.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        gr[u].push_back({v, w});
        gr[v].push_back({u, w});
        sum += 2 * w;
    }
    if (n == 1) {
        for (int j = 0; j < q; ++j) {
            int t;
            cin >> t;
            if (t == 1) {
                int ind;
                cin >> ind; --ind;
                if (s[ind] == '0') {
                    s[ind] = '1';
                }
                else {
                    s[ind] = '0';
                }
            }
            else {
                int l, r;
                cin >> l >> r; --l; --r;
                if (s[l] == '0') cout << "-1\n";
                else cout << "0\n";
            }
        }
        return;
    }
    dfs(0, -1);
    vector<pair<int, int>> eeee;
    for (int i = 0; i < n; ++i)
        eeee.push_back({dd[i], i});
    sp.build(eeee);
    for (int i = 1; i < n; ++i) {
        if (gr[i].size() == 1) lolkek.push_back(i);
    }
    for (auto i : lolkek) {
        for (auto j : lolkek) {
            int xi = i, xj = j;
            while (xi != xj) {
                if (h[xi] >= h[xj]) xi = pr[xi];
                else xj = pr[xj];
            }
            d[{i, j}] = h[xi];
        }
    }
    // for (auto e : lol) cout << e << '\n';
    map<int, int> lol5;
    for (int i = 0; i < lolkek.size(); ++i) lol5[lolkek[i]] = i;
    for (int i = 0; i < n; ++i) lol[i] = lol5[lol[i]];
    vector<SegmentTree> xx(lolkek.size());
    for (int i = 0; i < lolkek.size(); ++i) {
        // for (auto e : backlol[lolkek[i]]) cout << e << ' '; cout << endl;
        xx[i].build(backlol[lolkek[i]]);
    }
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') {
            xx[lol[i]].update(i, h[i]);
        }
    }
    int log2n = 20;
    pr[0] = 0;
    vector<vector<int>> binups(log2n, vector<int>(n));
    for (int i = 0; i < n; ++i) binups[0][i] = pr[i];
    for (int i = 1; i < log2n; ++i) {
        for (int j = 0; j < n; ++j) {
            binups[i][j] = binups[i - 1][binups[i - 1][j]];
        }
    }
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int ind;
            cin >> ind; --ind;
            if (s[ind] == '0') {
                s[ind] = '1';
                xx[lol[ind]].update(ind, h[ind]);
            }
            else {
                s[ind] = '0';
                xx[lol[ind]].update(ind, -1);
            }
        }
        else {
            int l, r;
            cin >> l >> r; --l; --r;
            set<int> cur;
            int ans = 0;
            int uppest = -1;
            int ct = 0;
            for (int i = 0; i < lolkek.size(); ++i) {
                // cout << "FUCK" << endl;
                Node tt = xx[i].get(l, r + 1);
                if (tt.mn == (int)1e16) {
                    // ans += 2 * fuckfuck[lolkek[i]];
                    continue;
                }
                // if (uppest == -1) {
                //     uppest = lol2[lolkek[i]][tt.mn];
                // }
                // else {
                //     int v = lol2[lolkek[i]][tt.mn];
                //     if (tin[uppest] < tin[v] && tout[uppest] > tout[v]) {}
                //     else if (tin[uppest] > tin[v] && tout[uppest] < tout[v]) {
                //         uppest = v;
                //     }
                //     else {
                //         for (int i = 19; i >= 0; --i) {
                //             if (tin[binups[i][uppest]] < tin[v] && tout[binups[i][uppest]] > tout[v]) continue;
                //             uppest = binups[i][uppest];
                //         }
                //         uppest = pr[uppest];
                //     }
                // }
                // ct++;
                // cur.insert(lol2[lolkek[i]][tt.mx]);
                // ans += 2 * tt.mx;
                // cout << lol2[lolkek[i]][tt.mn] << ' ' << lol2[lolkek[i]][tt.mx] << endl;
                cur.insert(lol2[lolkek[i]][tt.mn]);
                cur.insert(lol2[lolkek[i]][tt.mx]);
            }
            if (cur.size() == 0) {
                cout << "-1\n";
                continue;
            }
            // if (uppest == -1) {
            //     cout << "-1\n";
            //     continue;
            // }
            // for (auto e : cur) {
            //     bool ok = 1;
            //     for (auto i : cur) {
            //         if (tin[e] < tin[i] && tout[e] > tout[i]) ok = 0;
            //     }
            //     // if (ok) cout << "X" << e << endl;
            //     if (ok) ans += 2 * (h[lolkek[lol[e]]] - h[e]);
            // }
            // cout << sum - 2 * uppest - ans << '\n';
            vector<int> xx;
            for (auto e : cur) xx.push_back(e);
            sort(all(xx), [&](int i, int j) {
                return tin[i] < tin[j];
            });
            int curr = xx[xx.size() - 1];
            for (auto e : xx) {
                // cout << e << endl;
                ans += D(curr, e);
                curr = e;
            }
            cout << (dist(xx) - 1) * 2 << "\n";
        }
    }
}

signed main() {
    int tc = 1;
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#endif
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: