oj.uz

Submission #138718

# Submission time Handle Problem Language Result Execution time Memory
138718 2019-07-30T09:07:21 Z MrBrionix Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1004 ms 65056 KB 
//#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
/*
#define MAX_N 100005
#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));
}
*/

vector<int> grafo[100005],peso[100005];
int sol[100005][2],n,m,tmp;
priority_queue<pair<int,int> > pq;
bool ok[100005];
/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1
3
4


7 6 4
0 1 5
0 2 3
1 3 3
1 4 5
2 5 2
2 6 6
3 4 5 6
*/

void dfs(int nodo){
    
    for(int i=0;i<grafo[nodo].size();i++){
        
        if(sol[grafo[nodo][i]][0]==-1 || sol[grafo[nodo][i]][0]>(sol[nodo][1]+peso[nodo][i])){
            sol[grafo[nodo][i]][1]=sol[grafo[nodo][i]][0];
            sol[grafo[nodo][i]][0]=sol[nodo][1]+peso[nodo][i];
            if(sol[grafo[nodo][i]][1]!=-1){
                pq.push({-sol[grafo[nodo][i]][1],grafo[nodo][i]});
                ok[grafo[nodo][i]]=true;
            }
        }
        else{
            if(sol[grafo[nodo][i]][1]==-1 || sol[grafo[nodo][i]][1]>(sol[nodo][1]+peso[nodo][i])){
                sol[grafo[nodo][i]][1]=sol[nodo][1]+peso[nodo][i];
                pq.push({-sol[grafo[nodo][i]][1],grafo[nodo][i]});
                ok[grafo[nodo][i]]=true;
            }
        }
        
    }
    ok[nodo]=false;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    
    for(int i=0;i<M;i++){
        grafo[R[i][0]].push_back(R[i][1]);
        grafo[R[i][1]].push_back(R[i][0]);
        peso[R[i][0]].push_back(L[i]);
        peso[R[i][1]].push_back(L[i]);
    }
    
    for(int i=0;i<N;i++)sol[i][0]=sol[i][1]=-1;
    
    for(int i=0;i<K;i++){
        sol[P[i]][0]=sol[P[i]][1]=0;
        ok[P[i]]=true;
        pq.push({0,P[i]});
    }
    
    while(pq.size()>0){
        tmp=pq.top().second;
        pq.pop();
        
        if(ok[tmp]){
            dfs(tmp);
            ok[tmp]=false;
        }
        //if(tmp==0)break;
    }
    
    //for(int i=0;i<N;i++)cout<<sol[i][0]<<" "<<sol[i][1]<<endl;
    
    return sol[0][1];
}



/*

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

  return 0;
}
*/

Compilation message

crocodile.cpp: In function 'void dfs(int)':
crocodile.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 9 ms 5112 KB Output is correct
5 Correct 7 ms 5176 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 8 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 9 ms 5112 KB Output is correct
5 Correct 7 ms 5176 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 8 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5108 KB Output is correct
11 Correct 9 ms 5116 KB Output is correct
12 Correct 10 ms 5496 KB Output is correct
13 Correct 11 ms 5496 KB Output is correct
14 Correct 7 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 9 ms 5112 KB Output is correct
5 Correct 7 ms 5176 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 8 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 8 ms 5108 KB Output is correct
11 Correct 9 ms 5116 KB Output is correct
12 Correct 10 ms 5496 KB Output is correct
13 Correct 11 ms 5496 KB Output is correct
14 Correct 7 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 755 ms 59716 KB Output is correct
17 Correct 114 ms 17784 KB Output is correct
18 Correct 150 ms 19576 KB Output is correct
19 Correct 1004 ms 65056 KB Output is correct
20 Correct 360 ms 52868 KB Output is correct
21 Correct 58 ms 10616 KB Output is correct
22 Correct 405 ms 49096 KB Output is correct