oj.uz

Submission #28600

# Submission time Handle Problem Language Result Execution time Memory
28600 2017-07-16T07:51:34 Z 맞왜틀 맞왜틀 신나는노래~ 헤이! 나도한번 불러보자(#1216, skdudn321, choiking10) Alternative Mart (FXCUP2_mart) C++11
0 / 1
 3219 ms 80108 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() > 25) 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 0 ms 3524 KB Output is correct
6 Correct 3 ms 3524 KB Output is correct
7 Correct 6 ms 3800 KB Output is correct
8 Correct 6 ms 3656 KB Output is correct
9 Correct 236 ms 22336 KB Output is correct
10 Correct 63 ms 8504 KB Output is correct
11 Correct 79 ms 5956 KB Output is correct
12 Correct 66 ms 5248 KB Output is correct
13 Correct 2189 ms 80100 KB Output is correct
14 Correct 2196 ms 80108 KB Output is correct
15 Correct 83 ms 7160 KB Output is correct
16 Correct 86 ms 6692 KB Output is correct
17 Correct 786 ms 14640 KB Output is correct
18 Correct 489 ms 12896 KB Output is correct
19 Correct 1939 ms 25712 KB Output is correct
20 Correct 1046 ms 19760 KB Output is correct
21 Correct 1599 ms 25684 KB Output is correct
22 Correct 1303 ms 19944 KB Output is correct
23 Correct 1959 ms 25852 KB Output is correct
24 Correct 1929 ms 22912 KB Output is correct
25 Correct 1939 ms 31996 KB Output is correct
26 Correct 1993 ms 22912 KB Output is correct
27 Correct 86 ms 7936 KB Output is correct
28 Correct 139 ms 7380 KB Output is correct
29 Correct 1016 ms 16684 KB Output is correct
30 Correct 876 ms 14724 KB Output is correct
31 Correct 2423 ms 32004 KB Output is correct
32 Correct 1893 ms 22580 KB Output is correct
33 Correct 2206 ms 31880 KB Output is correct
34 Correct 2756 ms 32396 KB Output is correct
35 Correct 2399 ms 32128 KB Output is correct
36 Correct 2033 ms 32392 KB Output is correct
37 Correct 2316 ms 49184 KB Output is correct
38 Correct 2819 ms 52880 KB Output is correct
39 Correct 199 ms 8296 KB Output is correct
40 Correct 219 ms 8296 KB Output is correct
41 Correct 1326 ms 20004 KB Output is correct
42 Correct 1416 ms 20148 KB Output is correct
43 Correct 3199 ms 48756 KB Output is correct
44 Correct 2446 ms 50080 KB Output is correct
45 Correct 2709 ms 48536 KB Output is correct
46 Correct 2943 ms 49736 KB Output is correct
47 Correct 2699 ms 48392 KB Output is correct
48 Correct 2956 ms 49448 KB Output is correct
49 Correct 3173 ms 48524 KB Output is correct
50 Correct 3219 ms 49316 KB Output is correct
51 Incorrect 2043 ms 47996 KB Output isn't correct
52 Halted 0 ms 0 KB -