Submission #28594

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28594	2017-07-16T07:46:52 Z	맞왜틀 맞왜틀 신나는노래~ 헤이! 나도한번 불러보자(#1216, skdudn321, choiking10)	Alternative Mart (FXCUP2_mart)	C++11	0 / 1	1022 ms	42848 KB

mart

#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() > 10) 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	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	89 ms	8512 KB	Output is correct
10	Correct	63 ms	8504 KB	Output is correct
11	Correct	46 ms	4720 KB	Output is correct
12	Correct	36 ms	4592 KB	Output is correct
13	Correct	909 ms	42840 KB	Output is correct
14	Correct	889 ms	42848 KB	Output is correct
15	Correct	133 ms	7160 KB	Output is correct
16	Correct	113 ms	6692 KB	Output is correct
17	Correct	803 ms	14640 KB	Output is correct
18	Correct	416 ms	12896 KB	Output is correct
19	Correct	866 ms	14504 KB	Output is correct
20	Correct	613 ms	13032 KB	Output is correct
21	Correct	636 ms	16012 KB	Output is correct
22	Correct	469 ms	13080 KB	Output is correct
23	Correct	873 ms	19252 KB	Output is correct
24	Correct	653 ms	16048 KB	Output is correct
25	Correct	593 ms	19252 KB	Output is correct
26	Correct	599 ms	16180 KB	Output is correct
27	Correct	156 ms	7936 KB	Output is correct
28	Correct	103 ms	7380 KB	Output is correct
29	Correct	1022 ms	16684 KB	Output is correct
30	Correct	876 ms	14724 KB	Output is correct
31	Incorrect	953 ms	19260 KB	Output isn't correct
32	Halted	0 ms	0 KB	-