QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#708481#9431. The Quest for El DoradoFiatiustitiaWA 116ms8232kbC++203.7kb2024-11-03 22:49:202024-11-03 22:49:21

Judging History

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

  • [2024-11-03 22:49:21]
  • 评测
  • 测评结果:WA
  • 用时:116ms
  • 内存:8232kb
  • [2024-11-03 22:49:20]
  • 提交

answer

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

struct info
{
    int mx;
    info(int a = 0) : mx(a) {}
    friend info operator+(const info &a, const info &b)
    {
        return info(max(a.mx, b.mx));
    }
};
struct sparse_table
{
    static constexpr int N = 5e5 + 7;
    static int lg[N];
    static void init()
    {
        for (int i = 2; i < N; i++)
            lg[i] = lg[i >> 1] + 1;
    }
    vector<array<info, 20>> val;
    sparse_table(int n = 0) : val(n) {}
    info &operator[](int x) { return val[x][0]; }
    const info operator[](int x) const { return val[x][0]; }
    void build()
    {
        const int n = val.size(), len = lg[n];
        for (int i = 1; i <= len; i++)
            for (int l = 0; l + (1 << i) - 1 < n; l++)
                val[l][i] = val[l][i - 1] + val[l + (1 << i - 1)][i - 1];
    }
    info query(int l, int r)
    {
        const int dep = lg[r - l + 1];
        return val[l][dep] + val[r - (1 << dep) + 1][dep];
    }
    int getpos(int p, int w)
    {
        int len = val.size();
        for (int i = 19; i >= 0 && p < len; i--)
            if ((p + (1 << i)) < len && val[p][i].mx < w)
                p = p + (1 << i);
        if (p < len && val[p][0].mx < w)
            p++;
        return p;
    }
};
int sparse_table::lg[N] = {0};

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    using E = array<int, 3>;
    using W = pair<int, int>;
    vector g(n + 1, vector<E>());
    vector<sparse_table> S(m + 1);
    vector<W> tar(k);
    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 pos(m + 1, vector<int>());
    for (int i = 0; i < k; i++)
    {
        auto &[c, l] = tar[i];
        cin >> c >> l;
        S[c].val.push_back({0});
        S[c].val.back()[0] = info(l);
        pos[c].push_back(i);
    }
    for (int i = 1; i <= m; i++)
    {
        pos[i].push_back(k);
    }
    for (int i = 1; i <= m; i++)
        S[i].build();
    vector<W> dis(n + 1, W(n + 1, 1e9));
    dis[1] = {0, 0};
    using NODE = pair<W, int>;
    priority_queue<NODE, vector<NODE>, greater<NODE>> q;
    q.push(NODE(W(0, 0), 1));
    vector<bool> vis(n + 1);

    while (!q.empty())
    {
        auto [D, u] = q.top();
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        auto [no, disu] = D;
        for (auto [v, c, l] : g[u])
        {
            if (vis[v])
                continue;
            if (tar[no].first == c && disu + l <= tar[no].second)
            {
                dis[v] = min(dis[v], W(no, disu + l));
                q.push(NODE(dis[v], v));
            }
            else
            {
                auto p = upper_bound(pos[c].begin(), pos[c].end(), no);
                if (p == pos[c].end())
                    continue;
                auto np = S[c].getpos(p - pos[c].begin(), l);
                if (np < pos[c].size() - 1)
                {
                    assert(tar[pos[c][np]].second >= l);
                    dis[v] = min(dis[v], W(pos[c][np], l));
                    q.push(NODE(dis[v], v));
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << (dis[i].first < n ? 1 : 0);
    cout << '\n';
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
    auto _ = clock();
#endif
    sparse_table::init();
    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: 1ms
memory: 5480kb

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: 116ms
memory: 8232kb

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
1100010010101011011011000000011000001100001000
1000000000000000000000000000000000000000000000
1011000000000000000100010011000100000000000010
1000000000000000000000000000000000000000000000
1001100010110000100001100000000011001110110
101010000000000000010...

result:

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