oj.uz

Submission #1090709

# Submission time Handle Problem Language Result Execution time Memory
1090709 2024-09-18T15:39:47 Z AlgorithmWarrior Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 264 ms 129828 KB 
#include <bits/stdc++.h>
#define MAX 3000005

using namespace std;

int N,M,K;
struct edge
{
    int nod;
    int len;
};
class cmp
{
public:
    bool operator()(edge a,edge b)
    {
        return a.len>b.len;
    }
};
vector<edge>G[MAX];
priority_queue<edge,vector<edge>,cmp>pq;
int dist1[MAX],dist2[MAX];

void read(int N,int M,int R[][2],int L[],int K,int P[])
{
    while(M--)
    {
        int nod1,nod2,len;
        nod1=R[M][0];
        nod2=R[M][1];
        len=L[M];
        ++nod1;
        ++nod2;
        G[nod1].push_back({nod2,len});
        G[nod2].push_back({nod1,len});
    }
    int i;
    for(i=1;i<=N;++i)
        dist1[i]=dist2[i]=1e9+100000000;
    while(K--)
    {
        int nod;
        nod=P[K];
        ++nod;
        dist1[nod]=dist2[nod]=0;
        pq.push({nod,0});
    }
}

void djikstra()
{
    while(!pq.empty() && pq.top().nod!=1)
    {
        int nod=pq.top().nod;
        int len=pq.top().len;
        pq.pop();
        if(len>dist2[nod])
            continue;
        for(auto per : G[nod])
        {
            int nod2=per.nod;
            int len2=per.len;
            if(dist2[nod2]>len+len2)
            {
                if(dist1[nod2]>len+len2)
                {
                    dist2[nod2]=dist1[nod2];
                    dist1[nod2]=len+len2;
                }
                else
                    dist2[nod2]=len+len2;
                if(dist2[nod2]<=1e9)
                    pq.push({nod2,dist2[nod2]});
            }
        }
    }
}

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
    read(N,M,R,L,K,P);
    djikstra();
    return dist2[1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 71516 KB Output is correct
2 Correct 24 ms 71772 KB Output is correct
3 Correct 25 ms 71516 KB Output is correct
4 Correct 24 ms 71692 KB Output is correct
5 Correct 22 ms 71512 KB Output is correct
6 Correct 22 ms 71516 KB Output is correct
7 Correct 22 ms 71516 KB Output is correct
8 Correct 21 ms 71588 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 71516 KB Output is correct
2 Correct 24 ms 71772 KB Output is correct
3 Correct 25 ms 71516 KB Output is correct
4 Correct 24 ms 71692 KB Output is correct
5 Correct 22 ms 71512 KB Output is correct
6 Correct 22 ms 71516 KB Output is correct
7 Correct 22 ms 71516 KB Output is correct
8 Correct 21 ms 71588 KB Output is correct
9 Correct 22 ms 71772 KB Output is correct
10 Correct 21 ms 71516 KB Output is correct
11 Correct 23 ms 71516 KB Output is correct
12 Correct 23 ms 72028 KB Output is correct
13 Correct 22 ms 71992 KB Output is correct
14 Correct 22 ms 71512 KB Output is correct
15 Correct 22 ms 71516 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 71516 KB Output is correct
2 Correct 24 ms 71772 KB Output is correct
3 Correct 25 ms 71516 KB Output is correct
4 Correct 24 ms 71692 KB Output is correct
5 Correct 22 ms 71512 KB Output is correct
6 Correct 22 ms 71516 KB Output is correct
7 Correct 22 ms 71516 KB Output is correct
8 Correct 21 ms 71588 KB Output is correct
9 Correct 22 ms 71772 KB Output is correct
10 Correct 21 ms 71516 KB Output is correct
11 Correct 23 ms 71516 KB Output is correct
12 Correct 23 ms 72028 KB Output is correct
13 Correct 22 ms 71992 KB Output is correct
14 Correct 22 ms 71512 KB Output is correct
15 Correct 22 ms 71516 KB Output is correct
16 Correct 235 ms 125904 KB Output is correct
17 Correct 61 ms 82516 KB Output is correct
18 Correct 70 ms 83540 KB Output is correct
19 Correct 264 ms 129828 KB Output is correct
20 Correct 184 ms 118352 KB Output is correct
21 Correct 41 ms 76624 KB Output is correct
22 Incorrect 190 ms 114772 KB Output isn't correct
23 Halted 0 ms 0 KB -