QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710776#9431. The Quest for El DoradolibantianWA 81ms5168kbC++231.8kb2024-11-04 21:41:592024-11-04 21:42:01

Judging History

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

  • [2024-11-04 21:42:01]
  • 评测
  • 测评结果:WA
  • 用时:81ms
  • 内存:5168kb
  • [2024-11-04 21:41:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    using E = array<int, 3>;
    using P = pair<int64_t, int64_t>;
    vector<E> g[n + 1];

    for (int i = 0; i < m; i++)
    {
        int u, v, c, l;
        cin >> u >> v >> c >> l;
        g[u].push_back({v, c, l});
        g[v].push_back({u, c, l});
    }
    vector<int> vis(n + 1);
    vector<priority_queue<P>> q(m + 1);
    vis[1] = 1;
    for (auto [v, c, l] : g[1])
        q[c].push(P(-l, v));
    for (int it = 0; it < k; it++)
    {
        int C, L;
        cin >> C >> L;
        vector<P> tmp;
        while (!q[C].empty())
        {
            auto [l, u] = q[C].top();
            l = -l;
            if (l > L)
                break;
            q[C].pop();
            if (vis[u])
                continue;
            vis[u] = 1;
            for (auto [v, c, w] : g[u])
            {
                if (vis[v])
                    continue;
                if (c == C)
                {
                    //tmp.push_back(P(-w, v));
                    q[c].push(P(-(l + w), v));
                }
                else
                {
                    q[c].push(P(-w, v));
                }
            }
        }
        // for(auto [l,u] : tmp)
        // {
        //     if (vis[u])
        //         continue;
        //     q[C].push(P(l,u));
        // }
    }
    for(int i = 1;i <= n;i++)
        cout << vis[i];
    cout << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    auto _ = clock();
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
#ifdef LOCAL
    cerr << clock() - _ << '\n';
#endif
    return 0;
}

详细

Test #1:

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

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: 81ms
memory: 5168kb

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
1000000010101001011011000000001000000100001000
1000000000000000000000000000000000000000000000
1011000000000000000100000010000000000000000010
1000000000000000000000001000010000001001000001
1001100010100000100001100000000011001110110
100010000000000000010...

result:

wrong answer 2nd lines differ - expected: '1100010010111011011011000000011000001100001000', found: '1000000010101001011011000000001000000100001000'