Submission #18381

#	Time	Username	Problem	Language	Result	Execution time	Memory
18381		atomzeno	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	678 ms	176428 KiB

crocodile

#include "crocodile.h"
#include<vector>
#include<algorithm>
#include<queue>
#define NN 100001
#define MM 1000001
using namespace std;
int n,m,k,num[NN];
long long val[NN][2];
bool check[NN];
struct ST{int s,e,val;}A[MM];
struct SST{int s,val;}B[MM],o;
vector<SST> ND[NN];
priority_queue<pair<int,int> > bfs;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    int i;
    int loc2,val2,loc,len;
    n=N,m=M,k=K;
    for(i=0;i<n;i++){
        val[i][0]=val[i][1]=1000000001;
        check[i]=0;
    }
    for(i=0;i<m;i++){A[i].s=R[i][0],A[i].e=R[i][1],A[i].val=L[i];}
    for(i=0;i<m;i++){
        o.s=A[i].s,o.val=A[i].val;
        ND[A[i].e].push_back(o);
        o.s=A[i].e,o.val=A[i].val;
        ND[A[i].s].push_back(o);
        num[A[i].e]++,num[A[i].s]++;
    }
    for(i=0;i<k;i++){
        val[P[i]][0]=0,val[P[i]][1]=0;
        bfs.push(make_pair(0,P[i]));
    }
    for(;!bfs.empty();){
        loc=(bfs.top()).second;
        if(check[loc]==0){
            len=num[loc];
            for(i=0;i<len;i++){
                if(val[ND[loc][i].s][0]>(val[loc][1]+ND[loc][i].val)){
                    val[ND[loc][i].s][1]=val[ND[loc][i].s][0];
                    val[ND[loc][i].s][0]=(val[loc][1]+ND[loc][i].val);
                    bfs.push(make_pair(val[ND[loc][i].s][1]*(-1),ND[loc][i].s));
                }
                else if(val[ND[loc][i].s][1]>(val[loc][1]+ND[loc][i].val)){
                    val[ND[loc][i].s][1]=(val[loc][1]+ND[loc][i].val);
                    bfs.push(make_pair(val[ND[loc][i].s][1]*(-1),ND[loc][i].s));
                }
            }
            check[loc]=1;
        }
        bfs.pop();
    }
    return val[0][1];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11