QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669166#9431. The Quest for El DoradomulberryRE 10ms3608kbC++234.2kb2024-10-23 17:30:092024-10-23 17:30:20

Judging History

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

  • [2024-10-23 17:30:20]
  • 评测
  • 测评结果:RE
  • 用时:10ms
  • 内存:3608kb
  • [2024-10-23 17:30:09]
  • 提交

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;
        // cout << "col " << i << '\n';
        // for (auto [x, y] : col[i]) cout << x << ' ' << y << '\n';
        auto &a = col[i];
        auto &v = mx[i];
        for (int k = 0; k <= 18; k++) v[k].resize(a.size(), 0);
        int n = a.size() - 1;
        for (int j = 0; 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;
                };
                int st = find(now + 1);
                if (st == -1) 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 << '\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--) {
                        if (a[v[x][i]].second < val &&
                            x + (1 << i) < a.size()) {
                            x += (1 << i);
                        }
                    }
                    // cout << "after " << x << '\n';
                    if (a[v[x][0]].second >= val) return a[v[x][0]].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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 3608kb

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

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:


result: