QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#669333#9431. The Quest for El DoradomulberryWA 87ms6852kbC++234.4kb2024-10-23 18:12:502024-10-23 18:12:51

Judging History

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

  • [2024-10-23 18:12:51]
  • 评测
  • 测评结果:WA
  • 用时:87ms
  • 内存:6852kb
  • [2024-10-23 18:12:50]
  • 提交

answer

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int T, n, m, k;
vector<array<int, 3>> g[N];
vector<int> mx[N][20];
void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 1; i <= m; i++) {
        int u, v, c, val;
        cin >> u >> v >> c >> val;
        g[u].push_back({v, c, val});
        g[v].push_back({u, c, val});
    }
    vector<vector<pair<int, int>>> col(m + 1, vector<pair<int, int>>(1));
    vector<pair<int, int>> info(k + 1);
    vector<pair<int, int>> pos(k + 1);
    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        info[i] = {a, b};
        pos[i] = {a, col[a].size()};
        col[a].push_back({i, b});
    }
    for (int i = 1; i <= m; i++) {
        if (col[i].size() == 1) continue;
        auto &a = col[i];
        auto &v = mx[i];
        for (int k = 0; k <= 18; k++) {
            v[k].clear();
            v[k].resize(a.size(), 0);
        }
        int n = a.size() - 1;
        for (int j = 1; j < n; j++) v[0][j] = j + 1;
        for (int k = 1; k <= 18; k++)
            for (int j = 1; j <= n; j++) {
                int l = v[k - 1][j], r = v[k - 1][min(n, j + (1 << (k - 1)))];
                if (a[l].second < a[r].second)
                    v[k][j] = r;
                else
                    v[k][j] = l;
            }
    }
    vector<bool> vis(n + 1);
    priority_queue<array<int, 3>> q;
    q.push({0, 0, 1});
    while (!q.empty()) {
        auto [now, dis, x] = q.top();
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto [v, c, val] : g[x]) {
            if (vis[v]) continue;
            auto [C, Dis] = info[now];
            if (c == C && dis + val <= Dis) {
                q.push({now, dis + val, v});
            } else {
                if (col[c].size() == 1) continue;
                auto find = [&](int x) {
                    auto &a = col[c];
                    int l = 1, r = a.size() - 1;
                    while (l + 1 < r) {
                        int mid = (l + r) / 2;
                        if (a[mid].first < x)
                            l = mid;
                        else
                            r = mid;
                    }
                    if (a[l].first >= x)
                        return l;
                    else if (a[r].first >= x)
                        return r;
                    return -1;
                };
                auto &a = col[c];
                int st = lower_bound(a.begin() + 1, a.end(),
                                     pair<int, int>{now + 1, 0}) -
                         a.begin();
                if (st == a.size()) continue;
                // cout << "debug1 " << now << ' ' << dis << ' ' << x << '\n';
                // cout << "debug2 " << c << ' ' << st << ' ' <<
                // col[c][st].first
                //      << ' ' << col[c][st].second << '\n';
                // cout << "debug3 " << val << '\n';
                auto query = [&](int x, int val) {
                    // cout << "before " << x << ' ' << col[c][x].second <<
                    // '\n';
                    auto &a = col[c];
                    auto &v = mx[c];
                    if (a[x].second >= val) return a[x].first;
                    for (int i = 18; i >= 0; i--) {
                        // cout << v[x][i] << ' ' << a.size() << '\n';
                        if (a[v[i][x]].second < val &&
                            x + (1 << i) < a.size()) {
                            x += (1 << i);
                        }
                    }
                    // cout << "after " << x << '\n';
                    if (a[v[0][x]].second >= val) return a[v[0][x]].first;
                    return -1;
                };
                int newpos = query(st, val);
                if (newpos == -1) continue;
                // cout << "newpos " << newpos << '\n';
                assert(info[newpos].first == c);
                assert(info[newpos].second >= val);
                q.push({newpos, val, v});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 9ms
memory: 3784kb

input:

2
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 30
3 1 1
2 3 1 10
1 100

output:

11011
100

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 87ms
memory: 6852kb

input:

1110
46 80 30
44 23 5 46
10 28 1 64
32 34 3 40
9 36 1 26
15 14 5 95
38 19 2 34
2 17 4 183
10 38 2 81
5 15 2 83
31 38 3 100
40 30 1 53
41 10 1 193
29 20 5 18
14 41 3 78
8 16 5 74
46 13 3 78
44 28 3 45
1 40 3 133
5 32 1 108
22 26 2 83
10 38 1 77
11 40 1 11
17 21 2 66
41 46 3 98
9 36 2 25
40 18 1 19
27...

output:

1000110011110111110010100001010100100101000000
1100010010111011011011000000011000001100001000
1000000000000000000000000000000000000000000000
1011010000000010000100010011000100000000000010
1000000000000000000000101000010000000001000001
1001100010110000100001100000000011001110110
101010000000000000010...

result:

wrong answer 5th lines differ - expected: '1000000000000000000000101000010000001001000001', found: '1000000000000000000000101000010000000001000001'