QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#750093#9431. The Quest for El DoradoYuuTL 212ms10872kbC++233.3kb2024-11-15 12:36:032024-11-15 12:36:04

Judging History

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

  • [2024-11-15 12:36:04]
  • 评测
  • 测评结果:TL
  • 用时:212ms
  • 内存:10872kb
  • [2024-11-15 12:36:03]
  • 提交

answer

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

void sol(){
    int n, m, k;
    std::cin>>n>>m>>k;

    std::vector<std::map<int, std::set<std::array<int, 2>>>>G(n + 1);
    for(int i = 1;i <= m;i++){
        int u, v, c, cost;
        std::cin>>u>>v>>c>>cost;
        G[u][c].insert({cost, v});
        G[v][c].insert({cost, u});
    }

    auto del = [&](int u, int v, int c, int cost){
        G[u][c].erase({cost, v});
        if(G[u][c].size() == 0){
            G[u].erase(c);
        }
    };

    std::vector<std::map<int, std::set<int>>>SG(m + 1);
    
    {
        //  初始化边集
        std::vector<std::array<int, 4>>dell;
        for(auto& [c, E] : G[1]){
            for(auto& [cost, v] : E){
                SG[c][cost].insert(v);
                dell.push_back({1, v, c, cost});
            }
        }  

        for(auto [u, v, c, cost] : dell){
            del(u, v, c, cost);
            del(v, u, c, cost);
        }
    }

    const int inf = 2E18;
    std::vector<int>vis(n + 1);
    std::vector<int>dis(n + 1, inf);
    dis[1] = 0;
    vis[1] = 1;

    auto calc = [&](int c, int U){
        if(SG[c].size() == 0) return ;
        std::priority_queue<std::array<int, 2>, std::vector<std::array<int, 2>>, std::greater<>>Q;
        std::set<int>nw;
        std::vector<std::array<int, 2>>dl;
        for(auto& [cost, V] : SG[c]){
            if(cost > U) break;
            for(auto v : V){
                dl.push_back({cost, v});
                if(vis[v] == 0){
                    if(dis[v] > cost){
                        Q.push({dis[v] = cost, v});
                        nw.insert(v);
                    }
                }
            }
        }

        for(auto [cost, u] : dl){
            SG[c][cost].erase(u);
            if(SG[c][cost].size() == 0){
                SG[c].erase(cost);
            }
        }

        while(Q.size()){
            auto [d, u] = Q.top();
            Q.pop();
            
            if(dis[u] < d || G[u].count(c) == 0){
                continue ;
            }

            auto& E = G[u][c];
            for(auto [cost, v] : E){
                if(cost + d > U) break;
                if(vis[v] == 0 && dis[v] > cost + d){
                    Q.push({dis[v] = cost + d, v});
                    nw.insert(v);
                }
            }
        }

        //  加入新的点, 删除外点与内部点的边
        std::vector<std::array<int, 4>>dell;
        for(auto u : nw){
            vis[u] = 1;
        }
        for(auto u : nw){
            for(auto& [c, E] : G[u]){
                for(auto& [cost, v] : E){
                    if(vis[v] == 0){
                        dell.push_back({u, v, c, cost});
                        SG[c][cost].insert(v);
                    }
                }
            }
        }

        for(auto [u, v, c, cost] : dell){
            del(u, v, c, cost);
            del(v, u, c, cost);
        }
    };

    for(int i = 1;i <= k;i++){
        int c, U;
        std::cin>>c>>U;
        calc(c, U);
    }

    for(int i = 1;i <= n;i++){
        std::cout<<vis[i];
    }
    std::cout<<"\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; std::cin>>t;
    while(t--) sol();  
    return 0;
}

详细

Test #1:

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

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: 0
Accepted
time: 189ms
memory: 8944kb

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
1000000000000000000000101000010000001001000001
1001100010110000100001100000000011001110110
101010000000000000010...

result:

ok 1110 lines

Test #3:

score: 0
Accepted
time: 212ms
memory: 10872kb

input:

1110
41 95 66
37 16 1 93
8 38 13 61
41 25 7 10
40 26 13 90
18 34 12 84
29 21 7 22
32 41 10 52
20 17 18 273
41 31 2 163
17 11 20 316
24 14 7 35
1 5 7 39
26 38 13 48
10 15 14 154
4 7 12 8
13 6 20 139
18 9 10 90
16 33 7 54
9 35 5 39
36 31 17 9
10 20 17 74
37 34 13 6
7 9 9 153
12 7 18 173
5 7 3 194
21 3...

output:

11111010101111111011111111101111111111011
11111111111111111111111111111111111111101
11111111111111111111111111111111111111111
11011110111111111111111111111011111111111
10100010011110000001010100010110010000001
111111111111111111111111111111111111111111
100000000000100000000000000100100000000000
1000...

result:

ok 1110 lines

Test #4:

score: -100
Time Limit Exceeded

input:

1
200000 500000 179
94800 107033 1 16
64316 117022 8 184
105481 172922 2 53
37627 148708 9 37
179021 41825 10 29
177650 69319 5 20
144968 160008 6 68
54796 172626 2 201
35718 99731 3 127
45553 132280 2 433
199580 18097 1 116
77143 7273 7 90
49300 94594 8 231
52637 197546 8 62
156375 4265 2 54
136509...

output:

111111111011001111111110110111111100000111111111111011101111011111110011111111011111111101100111111111110100111111101111111111111111111111111111111111111111111101111111111111111101111101010111111111111111110111111110111110111011010001110111111111111101111110011111111111111111110110111101011111111111...

result: