oj.uz

Submission #28405

# Submission time Handle Problem Language Result Execution time Memory
28405 2017-07-16T05:21:15 Z 일단아무거나적어놓은팀이름(#1191, solarmagic, junodeveloper) Alternative Mart (FXCUP2_mart) C++14
0 / 1
 1889 ms 65540 KB 
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
int n, m, k, q;
int martIdx[50001];
priority_queue<pair<ll,int> > d[50001];
set<int> visited[50001];
vector<pair<ll,int> > dist[50001];
vector<pair<int,ll> > adj[50001];
void dijkstra() {
    priority_queue<pair<ll, pair<int, int> > > q;
    for(int i = 0; i < k; ++i) {
        q.push({0, {martIdx[i], martIdx[i]}});
    }
    while(!q.empty()) {
        int u = q.top().second.first;
        int from = q.top().second.second;
        ll c = -q.top().first; q.pop();
        if(visited[u].size() == 11 || visited[u].find(from) != visited[u].end()) continue;
        visited[u].insert(from);
        d[u].push({c, from});
        for(auto& t : adj[u]) {
            int to = t.first;
            ll cost = t.second;
            q.push({-(c + cost), {to, from}});
        }
    }
}
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for(int i = 0; i < k; ++i) scanf("%d", martIdx + i);
    for(int i = 0; i < m; ++i) {
        int a, b, v;
        scanf("%d%d%d", &a, &b, &v);
        adj[a].push_back({b, v});
        adj[b].push_back({a, v});
    }
    dijkstra();
    for(int i = 1; i <= n; ++i) {
        while(!d[i].empty()) {
            dist[i].push_back({d[i].top().first, d[i].top().second});
            d[i].pop();
        }
    }
    for(int i = 0; i < q; ++i) {
        int s, x;
        scanf("%d%d", &s, &x);
        ll mn = 1e18, rIdx = 1e18;
        bool closed[11] = {0};
        for(int j = 0, idx; j < x; ++j) {
            scanf("%d", &idx);
            for(int l = 0; l < dist[s].size(); ++l)
                if(dist[s][l].second == idx) closed[l] = 1;
        }
        for(int j = 0; j < dist[s].size(); ++j) {
            if(closed[j]) continue;
            if(dist[s][j].first < mn || (dist[s][j].first == mn && dist[s][j].second < rIdx)) {
                mn = dist[s][j].first;
                rIdx = dist[s][j].second;
            }
        }
        printf("%lld %lld\n", rIdx, mn);
    }
    return 0;
}

/*
4 5 2 4
1 4
1 2 5
2 4 5
4 3 5
3 1 5
2 3 1
3 0
1 1 1
2 1 4
4 0
*/

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:56:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int l = 0; l < dist[s].size(); ++l)
                              ^
mart.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < dist[s].size(); ++j) {
                          ^
mart.cpp:34:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &k, &q);
                                      ^
mart.cpp:35:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < k; ++i) scanf("%d", martIdx + i);
                                                        ^
mart.cpp:38:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &v);
                                    ^
mart.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &s, &x);
                              ^
mart.cpp:55:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &idx);
                              ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 0 ms 8472 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8620 KB Output is correct
6 Correct 0 ms 8620 KB Output is correct
7 Correct 0 ms 9000 KB Output is correct
8 Correct 6 ms 9000 KB Output is correct
9 Correct 96 ms 15408 KB Output is correct
10 Correct 76 ms 15396 KB Output is correct
11 Correct 73 ms 14020 KB Output is correct
12 Correct 79 ms 14020 KB Output is correct
13 Correct 909 ms 63844 KB Output is correct
14 Correct 936 ms 63864 KB Output is correct
15 Correct 159 ms 16540 KB Output is correct
16 Correct 169 ms 16392 KB Output is correct
17 Correct 1373 ms 61536 KB Output is correct
18 Correct 1129 ms 62064 KB Output is correct
19 Correct 1539 ms 63912 KB Output is correct
20 Correct 1126 ms 64440 KB Output is correct
21 Correct 1566 ms 64044 KB Output is correct
22 Correct 1459 ms 64364 KB Output is correct
23 Correct 1493 ms 64972 KB Output is correct
24 Correct 1519 ms 65020 KB Output is correct
25 Correct 1389 ms 65368 KB Output is correct
26 Correct 1516 ms 65540 KB Output is correct
27 Correct 163 ms 17224 KB Output is correct
28 Correct 169 ms 16920 KB Output is correct
29 Correct 1889 ms 62472 KB Output is correct
30 Correct 1596 ms 62196 KB Output is correct
31 Incorrect 1613 ms 64336 KB Output isn't correct
32 Halted 0 ms 0 KB -