oj.uz

Submission #16656

# Submission time Handle Problem Language Result Execution time Memory
16656 2015-09-03T04:42:02 Z CodingBug Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 444 ms 146380 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 143304 KB Output is correct
2 Correct 0 ms 143304 KB Output is correct
3 Correct 0 ms 143304 KB Output is correct
4 Correct 0 ms 143304 KB Output is correct
5 Correct 2 ms 143304 KB Output is correct
6 Correct 0 ms 143304 KB Output is correct
7 Correct 0 ms 143304 KB Output is correct
8 Correct 0 ms 143304 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 143304 KB Output is correct
2 Correct 0 ms 143304 KB Output is correct
3 Correct 0 ms 143304 KB Output is correct
4 Correct 0 ms 143304 KB Output is correct
5 Correct 0 ms 143304 KB Output is correct
6 Correct 0 ms 143304 KB Output is correct
7 Correct 0 ms 143304 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 144844 KB Output is correct
2 Correct 103 ms 143304 KB Output is correct
3 Correct 80 ms 143304 KB Output is correct
4 Correct 351 ms 146380 KB Output is correct
5 Correct 329 ms 143304 KB Output is correct
6 Correct 37 ms 143304 KB Output is correct
7 Correct 327 ms 143304 KB Output is correct