QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199294#6404. Shuttle TourUrgantTeamRE 0ms0kbC++235.7kb2023-10-04 04:45:132023-10-04 04:45:14

Judging History

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

  • [2023-10-04 04:45:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-04 04:45:13]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

struct pt {
    int to, w, node;
};

typedef long long ll;
int const maxn = 2e5 + 5, K = 55;
string s;
int numb[maxn], tmp = 1;
ll h[maxn], ans;
vector < pair < int, int > > g[maxn];
pair < int, int > dp[(1 << 20)][K];
pair < int, int > f[K];
vector < pt > G[K];
int ok[maxn], good[maxn];
int lst[maxn];

void dfs(int v, int p, int cur) {
    assert(cur < K);
    int flag = 1;
    lst[v] = p;
    numb[v] = cur;
    for (auto [u, w] : g[v]) {
        if (u == p) continue;
        h[u] = h[v] + w;
        if (flag) dfs(u, v, cur), flag = 0;
        else {
            G[cur].push_back({tmp, w, v});
            tmp++;
            dfs(u, v, tmp - 1);
        }
    }
}

inline pair < int, int > merge(pair < int, int > a, pair < int, int > b) {
    if (a.first == -1 || (b.first != -1 && h[a.first] > h[b.first])) a.first = b.first;
    if (a.second == -1 || (a.second != -1 && h[a.second] < h[b.second])) a.second = b.second;
    return a;
}

void build(int i, int l, int r) {
    if (r - l == 1) {
        for (int j = 0; j < tmp; j++) {
            dp[i][j] = {-1, -1};
        }
        if (s[l] == '1') dp[i][numb[l]] = {l, l};
    } else {
        int m = (r + l) / 2;
        build(2 * i + 1, l, m);
        build(2 * i + 2, m, r);
        for (int j = 0; j < tmp; j++) {
            dp[i][j] = merge(dp[2 * i + 1][j], dp[2 * i + 2][j]);
        }
    }
}

void update(int i, int l, int r, int lq) {
    if (r - l == 1) {
        assert(l == lq);
        if (s[lq] == '1') s[lq] = '0';
        else s[lq] = '1';
        for (int j = 0; j < tmp; j++) {
            dp[i][j] = {-1, -1};
        }
        if (s[l] == '1') dp[i][numb[l]] = {l, l};
    } else {
        int m = (r + l) / 2;
        if (lq < m) update(2 * i + 1, l, m, lq);
        else update(2 * i + 2, m, r, lq);
        for (int j = 0; j < tmp; j++) {
            dp[i][j] = merge(dp[2 * i + 1][j], dp[2 * i + 2][j]);
        }
    }
}

void get(int i, int l, int r, int lq, int rq) {
    if (lq >= r || l >= rq) return;
    if (lq <= l && r <= rq) {
        for (int j = 0; j < tmp; j++) f[j] = merge(f[j], dp[i][j]);
        return;
    }
    int m = (r + l) / 2;
    get(2 * i + 1, l, m, lq, rq);
    get(2 * i + 2, m, r, lq, rq);
}

void calc(int v) {
    ok[v] = 0;
    good[v] = 0;
    if (f[v].first != -1) ok[v] = 1, good[v] = 1;
    for (auto u : G[v]) {
        calc(u.to);
        ok[v] |= ok[u.to];
    }
}

void get(int v, int s) {
    for (auto u : G[v]) {
        s += ok[u.to];
    }
    s += good[v];
    for (auto u : G[v]) {
        if (s - ok[u.to] > 0) {
            f[u.to].first = u.node;
            if (f[u.to].second == -1) f[u.to].second = u.node;
            get(u.to, 1);
        } else {
            get(u.to, 0);
        }
        if (ok[u.to]) {
            if (f[v].second == -1 || h[f[v].second] < h[u.node]) f[v].second = u.node;
            if (f[v].first == -1 || h[f[v].first] > h[u.node]) f[v].first = u.node;
            if (f[v].first != -1 && f[v].second == -1) f[v].second = f[v].first;
            if (f[v].second != -1 && f[v].first == -1) f[v].first = f[v].second;
        }
    }
}

int check(int v, int p, int l, int r) {
    int ans = (l <= v && v <= r && s[v] == '1');
    for (auto [u, w] : g[v]) {
        if (u != p) ans |= check(u, v, l, r);
    }
    return ans;
}

main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q, u, v, w, l, r, type;
    cin >> n >> q;
    cin >> s;
    s = "#" + s;
    vector < vector < int > > edge;
    for (int i = 1; i < n; i++) {
        cin >> u >> v >> w;
        assert(w >= 0);
        edge.push_back({u, v, w});
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0, 0);
    assert(tmp < K);
    build(0, 1, n + 1);
    for (int i = 1; i <= q; i++) {
        cin >> type;
        if (type == 2) {
            cin >> l >> r;
            for (int j = 0; j < tmp; j++) f[j] = {-1, -1};
            get(0, 1, n + 1, l, r + 1);
            /*for (int j = 0; j < tmp; j++) {
                cout << f[j].first << " " << f[j].second << endl;
            }*/
            set < pair < int, int > > used;
            ans = 0;
            calc(0);
            get(0, 0);
            int flag = 0;
            for (int j = 0; j < tmp; j++) {
                if (f[j].first == -1) f[j].first = f[j].second;
                else if (f[j].second == -1) f[j].second = f[j].first;
                //cout << f[j].first << " " << f[j].second << endl;
                if (f[j].first != -1) {
                    ans += h[f[j].second] - h[f[j].first], flag = 1;
                    u = f[j].second, v = f[j].first;
                    while (u != v) {
                        assert(used.find({u, lst[u]}) == used.end());
                        used.insert({u, lst[u]});
                    }
                }
            }
            ll out;
            if (flag) out = 2 * ans;
            else out = -1;
            cout << out << '\n';
            ll res = -1;
            for (int j = l; j <= r; j++) {
                if (s[j] == '1') res = 0;
            }
            if (res == 0) {
                for (auto key : edge) {
                    assert(key[2] >= 0);
                    if (check(key[0], key[1], l, r) && check(key[1], key[0], l, r)) res += key[2];
                }
                res *= 2;
            }
            //assert(out == res);
        } else {
            cin >> u;
            update(0, 1, n + 1, u);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

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:


result: