oj.uz

Submission #392894

# Submission time Handle Problem Language Result Execution time Memory
392894 2021-04-22T08:03:25 Z Hazem Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1074 ms 78756 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
 
#define S second
#define F first
#define LL long long 
 
const int N1 = 2e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;

vector<pair<int,int>>adj[N1];
bool vis[N1];
LL mn1[N1],mn2[N1];

// LL dfs(int i){

//     if(vis[i])
//         return ans[i];

//     vis[i] = 1;
//     LL mn1 = LINF,mn2 = LINF;
//     for(auto x:adj[i]){
//         dfs(x.F);
//         if(ans[x.F]+x.S<mn1)mn2 = mn1,mn1 = ans[x.F]+x.S;
//         else if(ans[x.F]+x.S<mn2)mn2 = ans[x.F]+x.S;
//     }

//     ans1 = min(ans1,mn2);
//     return ans[i] = min(ans[i],mn2);
// }

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

    int n = N;
    
    for(int i=0;i<n;i++)
        mn1[i] = mn2[i] = LINF;

    for(int i=0;i<M;i++){
        adj[R[i][0]].push_back({R[i][1],L[i]});
        adj[R[i][1]].push_back({R[i][0],L[i]});
    }

    for(int i=0;i<K;i++)
        mn1[P[i]] = mn2[P[i]] = 0;
    
    priority_queue<pair<LL,int>>que;
    for(int i=0;i<n;i++)
        que.push({-mn2[i],i});

    while(!que.empty()){
        int u = que.top().S;
        LL ans = -que.top().F;
        que.pop();

        if(vis[u])continue;
        vis[u] = 1;

        //printf("%d %lld\n",u,ans);
        
        for(auto x:adj[u]){
            int v = x.F;
            //printf("%d %d %d\n",u,v,x.S);

            if(ans+x.S<mn1[v])
                mn2[v] = mn1[v],mn1[v] = ans+x.S;
            else 
                if(ans+x.S<mn2[v])
                    mn2[v] = ans+x.S;
            que.push({-mn2[v],v});
        }
    }
    return mn2[0];
}


/*
#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5324 KB Output is correct
10 Correct 3 ms 4988 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 10 ms 5708 KB Output is correct
13 Correct 9 ms 5708 KB Output is correct
14 Correct 4 ms 5012 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 6 ms 5324 KB Output is correct
10 Correct 3 ms 4988 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 10 ms 5708 KB Output is correct
13 Correct 9 ms 5708 KB Output is correct
14 Correct 4 ms 5012 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 932 ms 75412 KB Output is correct
17 Correct 148 ms 21048 KB Output is correct
18 Correct 175 ms 22708 KB Output is correct
19 Correct 1074 ms 78756 KB Output is correct
20 Correct 636 ms 60088 KB Output is correct
21 Correct 65 ms 11436 KB Output is correct
22 Correct 612 ms 50680 KB Output is correct