QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311041#6404. Shuttle Tourmemset0WA 124ms51612kbC++204.8kb2024-01-21 21:07:392024-01-21 21:07:40

Judging History

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

  • [2024-01-21 21:07:40]
  • 评测
  • 测评结果:WA
  • 用时:124ms
  • 内存:51612kb
  • [2024-01-21 21:07:39]
  • 提交

answer

#include <bits/stdc++.h>
#ifndef popteam
#define endl '\n'
#endif
#define all(x) begin(x), end(x)
using namespace std;
const int N = 2e5 + 9, M = 59;
int n, m, tot, nod, fa[N], bln[N], siz[N], out[M];
bool ok[N];
long long dep[N];
string s;
vector<int> leaves;
vector<pair<int, int>> G[N], child[M];
void dfs(int u) {
    siz[u] = 1;
    for (auto [v, w] : G[u])
        if (v != fa[u]) {
            fa[v] = u;
            dep[v] = dep[u] + w;
            dfs(v);
            siz[u] += siz[v];
        }
    if (siz[u] == 1) {
        leaves.push_back(u);
    }
}
struct atom {
    long long min, max;
    void reset() { min = LLONG_MAX, max = LLONG_MIN; }
    bool empty() { return min == LLONG_MAX && max == LLONG_MIN; }
    atom operator+(const atom &rhs) const {
        return {
            std::min(min, rhs.min),
            std::max(max, rhs.max),
        };
    }
} dp[M];
struct segtree {
    atom p[524288];
    void maintain(int u) {
        p[u].min = min(p[u << 1].min, p[u << 1 | 1].min);
        p[u].max = max(p[u << 1].max, p[u << 1 | 1].max);
    }
    void build(int u, int l, int r) {
        p[u].reset();
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void modify(int u, int k, bool op, int l, int r) {
        // fprintf(stderr, "modify %d %d %d %d %d\n", u, k, op, l, r);
        if (l == r) {
            if (op) {
                p[u].min = p[u].max = dep[k];
            } else {
                p[u].reset();
            }
            return;
        }
        int mid = (l + r) >> 1;
        if (k <= mid) {
            modify(u << 1, k, op, l, mid);
        } else {
            modify(u << 1 | 1, k, op, mid + 1, r);
        }
        maintain(u);
    }
    atom query(int u, int ql, int qr, int l, int r) {
        // fprintf(stderr, "query %d %d %d %d %d\n", u, ql, qr, l, r);
        if (ql == l && qr == r) {
            return p[u];
        }
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(u << 1, ql, qr, l, mid);
        if (ql > mid) return query(u << 1 | 1, ql, qr, mid + 1, r);
        return query(u << 1, ql, mid, l, mid) + query(u << 1 | 1, mid + 1, qr, mid + 1, r);
    }
} seg[M];
int main() {
#ifdef popteam
    freopen("K.in", "r", stdin);
#endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) {
        ok[i] = s[i - 1] == '1';
    }
    for (int u, v, w, i = 1; i < n; i++) {
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    dfs(1);
    memset(bln, -1, sizeof(bln));
    for (int i = 0; i < leaves.size(); i++) {
        seg[i].build(1, 1, n);
        int x = leaves[i];
        for (int u = x, lst = -1; u; lst = u, u = fa[u])
            if (bln[u] == -1) {
                bln[u] = i;
                if (ok[u]) {
                    seg[i].modify(1, u, true, 1, n);
                }
            } else {
                out[i] = u;
                child[bln[u]].emplace_back(i, lst);
                break;
            }
    }
    for (int i = 1; i <= n; i++)
        cerr << bln[i] << " \n"[i == n];
    for (int op, x, l, r, i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            ok[x] ^= 1;
            seg[bln[x]].modify(1, x, ok[x], 1, n);
        } else {
            cin >> l >> r;
            for (int i = leaves.size() - 1; i >= 0; i--) {
                dp[i] = seg[i].query(1, l, r, 1, n);
#ifdef popteam
                fprintf(stderr, "%d >> %lld %lld\n", i, dp[i].min, dp[i].max);
#endif
                int cnt = 0;
                for (auto [j, x] : child[i]) {
                    if (!dp[j].empty()) {
                        ++cnt;
                    }
                }
                for (auto [j, x] : child[i]) {
                    if (!dp[j].empty()) {
                        if (!dp[i].empty() || cnt > 1) {
                            dp[j] = dp[j] + atom{dep[fa[x]], dep[fa[x]]};
                        }
                    }
                }
                for (auto [j, x] : child[i]) {
                    if (!dp[j].empty()) {
                        dp[i] = dp[i] + atom{dep[fa[x]], dep[fa[x]]};
                    }
                }
            }
            bool ok = false;
            long long ans = 0;
            for (int i = 0; i < leaves.size(); i++) {
#ifdef popteam
                fprintf(stderr, "%d >> %lld %lld\n", i, dp[i].min, dp[i].max);
#endif
                if (!dp[i].empty()) {
                    ok = true;
                    ans += dp[i].max - dp[i].min;
                }
            }
            cout << (ok ? (ans << 1) : -1) << endl;
        }
    }
}

詳細信息

Test #1:

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

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: 124ms
memory: 51612kb

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:

17149847378
-1
26540740138
29613692754
21307948558
27003443184
11446581328
18332625722
20412196350
18655936942
29727468956
9146481114
6696272804
23682775470
14793879570
1983486788
14982588156
0
-1
7245018196
26193602866
20977405496
24807163344
17545090370
8533875940
7565207424
18079494744
0
27004673...

result:

wrong answer 7th numbers differ - expected: '11893407374', found: '11446581328'