oj.uz

Submission #28597

# Submission time Handle Problem Language Result Execution time Memory
28597 2017-07-16T07:48:54 Z 맞왜틀 맞왜틀 신나는노래~ 헤이! 나도한번 불러보자(#1216, skdudn321, choiking10) Alternative Mart (FXCUP2_mart) C++11
0 / 1
 1929 ms 79976 KB 
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
std::vector<std::pair<int,int>> G[50010];
std::vector<std::pair<int,int>> CK[50010];
struct node{
    int v, id, from;
};
bool operator<(node n1, node n2){
    return std::make_pair(-n1.v,n1.from) < std::make_pair(-n2.v,n2.from);
}
int main(){
    int N,M,K,Q;
    scanf("%d%d%d%d",&N,&M,&K,&Q);
    std::priority_queue<node> q;
    for(int i =0 ; i< K;i++){
        int v;
        scanf("%d",&v);
        q.push({0,v,v});
    }
    for(int i = 0; i < M ; i++){
        int A,B,C;
        scanf("%d%d%d",&A,&B,&C);
        G[A].push_back({B,C});
        G[B].push_back({A,C});
    }
    while(q.size() != 0){
        auto t = q.top();
        q.pop();
        if(CK[t.id].size() > 15) continue;
        bool flag = false;
        for(auto i : CK[t.id]){
            if(i.second == t.from) {
                flag = true;
                break;
            }
        }
        if(flag) continue;
        CK[t.id].push_back({t.v,t.from});

        for(auto i : G[t.id]){
            q.push({t.v+i.second,i.first,t.from});
        }
    }
    for(int i =0 ; i < Q;i ++){
        int S, X;
        scanf("%d%d",&S,&X);
        std::set<int> PC;
        for(int j =0; j < X; j++){
            int v;
            scanf("%d",&v);
            PC.insert(v);
        }
        std::sort(CK[S].begin(),CK[S].end());
        for(auto j : CK[S]){
            if(!PC.count(j.second)){
                printf("%d %d\n",j.second,j.first);
                break;
            }
        }
    }
}

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:16:34: 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:20:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&v);
                       ^
mart.cpp:25:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&A,&B,&C);
                                 ^
mart.cpp:49:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&S,&X);
                            ^
mart.cpp:53:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&v);
                           ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3524 KB Output is correct
2 Correct 0 ms 3524 KB Output is correct
3 Correct 0 ms 3524 KB Output is correct
4 Correct 0 ms 3524 KB Output is correct
5 Correct 3 ms 3524 KB Output is correct
6 Correct 0 ms 3524 KB Output is correct
7 Correct 0 ms 3668 KB Output is correct
8 Correct 3 ms 3656 KB Output is correct
9 Correct 143 ms 13120 KB Output is correct
10 Correct 66 ms 8504 KB Output is correct
11 Correct 86 ms 4912 KB Output is correct
12 Correct 43 ms 4592 KB Output is correct
13 Correct 1389 ms 79968 KB Output is correct
14 Correct 1376 ms 79976 KB Output is correct
15 Correct 126 ms 7160 KB Output is correct
16 Correct 109 ms 6692 KB Output is correct
17 Correct 769 ms 14640 KB Output is correct
18 Correct 269 ms 12896 KB Output is correct
19 Correct 1086 ms 16040 KB Output is correct
20 Correct 779 ms 13032 KB Output is correct
21 Correct 886 ms 16012 KB Output is correct
22 Correct 1056 ms 13080 KB Output is correct
23 Correct 1383 ms 19252 KB Output is correct
24 Correct 1279 ms 16048 KB Output is correct
25 Correct 1373 ms 19252 KB Output is correct
26 Correct 1353 ms 16180 KB Output is correct
27 Correct 179 ms 7936 KB Output is correct
28 Correct 143 ms 7380 KB Output is correct
29 Correct 1018 ms 16684 KB Output is correct
30 Correct 853 ms 14724 KB Output is correct
31 Correct 1163 ms 19260 KB Output is correct
32 Correct 1099 ms 15984 KB Output is correct
33 Correct 1253 ms 19268 KB Output is correct
34 Correct 1733 ms 28776 KB Output is correct
35 Correct 1449 ms 28376 KB Output is correct
36 Correct 1623 ms 29036 KB Output is correct
37 Correct 1669 ms 27716 KB Output is correct
38 Correct 1563 ms 28640 KB Output is correct
39 Correct 203 ms 8296 KB Output is correct
40 Correct 203 ms 8296 KB Output is correct
41 Correct 1326 ms 20004 KB Output is correct
42 Correct 1026 ms 20148 KB Output is correct
43 Correct 1823 ms 27288 KB Output is correct
44 Correct 1626 ms 27952 KB Output is correct
45 Correct 1779 ms 27200 KB Output is correct
46 Correct 1799 ms 27872 KB Output is correct
47 Correct 1929 ms 48788 KB Output is correct
48 Correct 1743 ms 27848 KB Output is correct
49 Correct 1806 ms 48656 KB Output is correct
50 Correct 1889 ms 49580 KB Output is correct
51 Incorrect 1143 ms 47996 KB Output isn't correct
52 Halted 0 ms 0 KB -