oj.uz

Submission #28638

# Submission time Handle Problem Language Result Execution time Memory
28638 2017-07-16T08:16:19 Z 맞왜틀 맞왜틀 신나는노래~ 헤이! 나도한번 불러보자(#1216, skdudn321, choiking10) Alternative Mart (FXCUP2_mart) C++11
1 / 1
 1556 ms 42848 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() > 11) 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
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 0 ms 3524 KB Output is correct
6 Correct 0 ms 3524 KB Output is correct
7 Correct 3 ms 3668 KB Output is correct
8 Correct 3 ms 3656 KB Output is correct
9 Correct 109 ms 13120 KB Output is correct
10 Correct 83 ms 8504 KB Output is correct
11 Correct 59 ms 4912 KB Output is correct
12 Correct 39 ms 4588 KB Output is correct
13 Correct 949 ms 42840 KB Output is correct
14 Correct 1069 ms 42848 KB Output is correct
15 Correct 66 ms 7160 KB Output is correct
16 Correct 63 ms 6692 KB Output is correct
17 Correct 516 ms 14640 KB Output is correct
18 Correct 319 ms 12896 KB Output is correct
19 Correct 603 ms 16040 KB Output is correct
20 Correct 433 ms 13028 KB Output is correct
21 Correct 613 ms 16012 KB Output is correct
22 Correct 476 ms 13080 KB Output is correct
23 Correct 623 ms 19252 KB Output is correct
24 Correct 946 ms 16048 KB Output is correct
25 Correct 906 ms 19252 KB Output is correct
26 Correct 936 ms 16184 KB Output is correct
27 Correct 146 ms 7936 KB Output is correct
28 Correct 133 ms 7380 KB Output is correct
29 Correct 1033 ms 16552 KB Output is correct
30 Correct 809 ms 14724 KB Output is correct
31 Correct 1063 ms 19260 KB Output is correct
32 Correct 919 ms 14444 KB Output is correct
33 Correct 669 ms 19268 KB Output is correct
34 Correct 836 ms 19652 KB Output is correct
35 Correct 1046 ms 19384 KB Output is correct
36 Correct 1119 ms 19648 KB Output is correct
37 Correct 1273 ms 27980 KB Output is correct
38 Correct 1249 ms 29036 KB Output is correct
39 Correct 163 ms 8296 KB Output is correct
40 Correct 186 ms 8296 KB Output is correct
41 Correct 1233 ms 20004 KB Output is correct
42 Correct 1406 ms 20144 KB Output is correct
43 Correct 1419 ms 27684 KB Output is correct
44 Correct 1366 ms 28348 KB Output is correct
45 Correct 1476 ms 27596 KB Output is correct
46 Correct 1376 ms 28268 KB Output is correct
47 Correct 1419 ms 27584 KB Output is correct
48 Correct 1453 ms 27980 KB Output is correct
49 Correct 1556 ms 27716 KB Output is correct
50 Correct 1523 ms 28112 KB Output is correct
51 Correct 1063 ms 27320 KB Output is correct
52 Correct 1026 ms 27584 KB Output is correct
53 Correct 443 ms 12104 KB Output is correct
54 Correct 1226 ms 19344 KB Output is correct
55 Correct 1213 ms 19416 KB Output is correct
56 Correct 1483 ms 28120 KB Output is correct
57 Correct 809 ms 42336 KB Output is correct