oj.uz

Submission #28644

# Submission time Handle Problem Language Result Execution time Memory
28644 2017-07-16T08:20:21 Z ㅁㄴㅇㄹ(#1150, TAMREF, Diuven, suhgyuho_william) Alternative Mart (FXCUP2_mart) C++11
0 / 1
 239 ms 14996 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> pt;
const int mx=50000, inf=1e9;
int N,M,K,Q;
vector<pii> G[mx];
pii dist[mx][12];
int hi[mx];
void input(){
    scanf("%d%d%d%d",&N,&M,&K,&Q);
    for(int i=0;i<K;i++){
        scanf("%d",&hi[i]);
    }
    for(int i=0,a,b,c;i<M;i++){
        scanf("%d%d%d",&a,&b,&c);
        G[a].push_back(mp(b,c));
        G[b].push_back(mp(a,c));
    }
    for(int i=0;i<mx;i++) fill(dist[i],dist[i]+11,mp(inf,0));
}
void dijk(){
    priority_queue<pt,vector<pt>,greater<pt>> q;
    for(int i=0;i<K;i++){
        dist[hi[i]][0]=mp(0,hi[i]);
        q.push(mp(dist[hi[i]][0],hi[i]));
    }
    pt u;
    int rodong;
    while(!q.empty()){
        u=q.top(); q.pop(); //u.va.va : cost, u.va.vb : source
        int p;
        if(dist[u.vb][10]<u.va) continue;
        for(pii x : G[u.vb]){ //x.va : vertex, x.vb : cost
            for(p=0;p<11;p++){
                if(dist[x.va][p].vb==u.va.vb){
                    if(dist[x.va][p].va>u.va.va+x.vb){
                        dist[x.va][p].va=u.va.va+x.vb;
                        q.push(mp(dist[x.va][p],x.va));
                        sort(dist[x.va],dist[x.va]+11);
                    }
                    goto term;
                }
            }
            for(p=11;p;p--) dist[x.va][p]=dist[x.va][p-1];
            for(int p=1;p<=11;p++){
                if(dist[x.va][p]>mp(u.va.va+x.vb,u.va.vb)){
                    dist[x.va][p-1]=mp(u.va.va+x.vb,u.va.vb);
                    q.push(mp(dist[x.va][p-1],x.va));
                    break;
                }else{
                    dist[x.va][p-1]=dist[x.va][p];
                }
            }
            term:
            rodong=rodong;
        }
    }
}
void debug(){
    for(int i=1;i<=N;i++){
        for(int j=0;j<11;j++){
            printf("(%d from %d) ",dist[i][j].va==inf?-1:dist[i][j].va,dist[i][j].vb);
        } puts("");
    }
}
void query(){
    int X,S,v;
    unordered_set<int> u;
    for(;Q--;){
        u.clear();
        scanf("%d%d",&S,&X);
        for(int i=0;i<X;i++){
            scanf("%d",&v);
            u.insert(v);
        }
        for(int i=0;i<11;i++){
            if(u.find(dist[S][i].vb)==u.end()){
                printf("%d %d\n",dist[S][i].vb,dist[S][i].va);
                break;
            }
        }
    }
}
int main(){
    //freopen("input.txt","rt",stdin);
    input();
    dijk();
    //debug();
    query();
}

Compilation message

mart.cpp: In function 'void input()':
mart.cpp:15: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:17:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&hi[i]);
                           ^
mart.cpp:20: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: In function 'void query()':
mart.cpp:76: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:78: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 8080 KB Output is correct
2 Correct 0 ms 8080 KB Output is correct
3 Correct 0 ms 8080 KB Output is correct
4 Correct 3 ms 8080 KB Output is correct
5 Correct 0 ms 8080 KB Output is correct
6 Correct 0 ms 8080 KB Output is correct
7 Correct 0 ms 8224 KB Output is correct
8 Correct 6 ms 8080 KB Output is correct
9 Correct 16 ms 8836 KB Output is correct
10 Correct 19 ms 8828 KB Output is correct
11 Correct 46 ms 8536 KB Output is correct
12 Correct 26 ms 8212 KB Output is correct
13 Correct 239 ms 14992 KB Output is correct
14 Correct 236 ms 14996 KB Output is correct
15 Runtime error 29 ms 9664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -