Submission #16656

#	Time	Username	Problem	Language	Result	Execution time	Memory
16656		CodingBug	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	444 ms	146380 KiB

crocodile

#include "crocodile.h"
#include <queue>
#define N 100000
#define M 1000000
#define INF 1000000000

using namespace std;

struct Inque{
    int x;
    int w;
    Inque(int _x=0,int _w=0):x(_x),w(_w){}
    bool operator<(const Inque &r)const{
        return w>r.w;
    }
};

int sta[N+1],chi[M*2+1],wei[M*2+1],nxt[M*2+1],m,n;
int d[2][N+1];
bool v[N+1];

priority_queue<Inque> Q;
void addEdge(int x,int y,int w,int p){
    nxt[p]=sta[x];
    chi[p]=y;
    wei[p]=w;
    sta[x]=p;
}

int travel_plan(int _n, int _m, int R[][2], int L[], int K, int P[])
{
    int i,j;

    n=_n; m=_m;

    for(i=0;i<m;i++){
        addEdge(R[i][0],R[i][1],L[i],i*2+1);
        addEdge(R[i][1],R[i][0],L[i],i*2+2);
    }

    for(i=0;i<n;i++){
        for(j=0;j<2;j++) d[j][i]=INF+1;
    }
    for(i=0;i<K;i++){
        for(j=0;j<2;j++) d[j][P[i]]=0;
        Q.push(Inque(P[i],0));
    }
    for(i=0;i<n;i++){
        while(!Q.empty() && v[Q.top().x]) Q.pop();
        if(Q.empty()) break;
        Inque t=Q.top(); Q.pop();
        if(t.x==0) break;
        v[t.x]=true;
        for(j=sta[t.x];j;j=nxt[j]){
            bool l=true;
            if(d[0][chi[j]]>t.w+wei[j]){
                d[1][chi[j]]=d[0][chi[j]];
                d[0][chi[j]]=t.w+wei[j];
            }
            else if(d[1][chi[j]]>t.w+wei[j]){
                d[1][chi[j]]=t.w+wei[j];
            }
            else{
                l=false;
            }
            if(l){
                if(d[1][chi[j]]!=INF+1){
                    Q.push(Inque(chi[j],d[1][chi[j]]));
                }
            }
        }
    }
    return d[1][0];
}

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