QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#646222#6404. Shuttle Tourcrimsonsunset#WA 52ms3844kbC++206.7kb2024-10-16 21:45:132024-10-16 21:45:14

Judging History

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

  • [2024-10-16 21:45:14]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:3844kb
  • [2024-10-16 21:45: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 = 1e9;
};
 
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 = 1e9;
            }
            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)1e9};
        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)1e9};
        return get(0, 0, sz, ql, qr);
    } 
};

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 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;
        dfs(e.first, v);
        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;

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[{lol[i], lol[j]}];
}

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    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});
    }
    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<int> lolkek;
    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]);
        }
    }
    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;
            for (int i = 0; i < lolkek.size(); ++i) {
    // cout << "FUCK" << endl;
                Node tt = xx[i].get(l, r + 1);
                if (tt.mn == (int)1e9) continue;
                // 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;
            }
            int curr = (*--cur.end());
            for (auto e : cur) {
                // cout << e << endl;
                ans += D(curr, e);
                curr = e;
            }
            cout << ans << "\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();
    }
}

詳細信息

Test #1:

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

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: 52ms
memory: 3844kb

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:

2788264120
-1
0
7086170248
2788264120
0
0
0
0
0
4297906128
-1
0
-1
-1
0
0
-1
-1
0
4297906128
-1
-1
-1
2716712308
2716712308
-1
-1
4297906128
-1
0
6281392916
-1
-1
-1
-1
1300013146
5774653100
-1
-1
-1
-1
0
-1
0
4297906128
-1
-1
3791166312
1300013146
1300013146
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

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