oj.uz

Submission #592296

# Submission time Handle Problem Language Result Execution time Memory
592296 2022-07-08T21:43:18 Z APROHACK Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 5 ms 3540 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
ll const NMX = 100001;
bool vis[NMX];
vector<pair<ll, int> >adj[NMX];
int bfsans[NMX];
int n;

void printBFSANS(){
  cout << "bfs number\n";
  for(int i = 0 ; i < n ; i++){

    cout << bfsans[i] << " ";
  }
  cout<<endl;
}
pair<ll, ll>dp[NMX];
pair<ll, ll>answer(int node){
  //cout<<" llegue "<<node<<endl;
  if(bfsans[node]==0)return dp[node]={0, 0};
  vis[node]=true;
  ll minimum1=LLONG_MAX, minimum2=LLONG_MAX;
  for(int i = 0 ; i < adj[node].size() ; i++){
    if(bfsans[adj[node][i].ss] == -1 || vis[adj[node][i].ss] || bfsans[adj[node][i].ss] > bfsans[node])continue;
    ll v;
    if(dp[adj[node][i].ss].ff == -1){
      pair<ll, ll>cur = answer(adj[node][i].ss);
      v = max(cur.ff, cur.ss) + adj[node][i].ff;
      if(cur.ff == -1 || cur.ss == -1)continue;
      
    }else{
      v = max(dp[adj[node][i].ss].ff, dp[adj[node][i].ss].ss) +  adj[node][i].ff;
    }
    
    if(v<minimum1){
        minimum2=minimum1;
        minimum1=v;
      }else if(v<minimum2){
        minimum2=v;
      }
  }
  vis[node]=false;
  if(minimum1==LLONG_MAX || minimum2 == LLONG_MAX){
    bfsans[node]=-1;
    return dp[node] = {-1, -1};
  }
  dp[node].ff=minimum1, dp[node].ss=minimum2;
  //cout<<"node: "<<node << " "<<minimum1 << " " << minimum2 << endl;
  return dp[node];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  memset(vis, false, sizeof vis);
  n=N;
  for(int i = 0 ; i <M  ; i++){
    adj[R[i][0]].pb({L[i], R[i][1]});
    adj[R[i][1]].pb({L[i], R[i][0]});
  }
  for(int i = 0 ; i < n ; i++)bfsans[i]=-1;
  queue<pair<ll, ll> >nodos;
  for(int i = 0 ; i < K ; i ++){
    nodos.push({0, P[i]});
    bfsans[P[i]]=0;
  }
  while(!nodos.empty()){
    pair<ll, ll> cur = nodos.front();
    nodos.pop();
    if(vis[cur.ss] )continue;
    ll cuenta = 0;
   // cout<<cur.ss << " ";
    for(int i = 0 ; i < adj[cur.ss].size() ; i++){
      if(bfsans[ adj[cur.ss][i].ss ] != -1)cuenta++;
      if(!vis[adj[cur.ss][i].ss]){
       // vis[adj[cur.ss][i].ss] = true;
        nodos.push({cur.ff+1, adj[cur.ss][i].ss});
        //cout << cur.ff+1 << " ";
        }
    }
    //cout<<endl;
    if(cuenta>=2){
      bfsans[cur.ss]=cur.ff;
      vis[cur.ss]=true;
    }
    if(bfsans[cur.ss]!=-1)vis[cur.ss]=true;
  }
  memset(vis, false, sizeof vis);
  //printBFSANS();
  for(int i = 0 ; i < n ; i ++){
    dp[i]={-1, -1};
  }
  pair<ll, ll>retu = answer(0);
  return max(retu.ff, retu.ss);
}

Compilation message

crocodile.cpp: In function 'std::pair<long long int, long long int> answer(int)':
crocodile.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = 0 ; i < adj[node].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0 ; i < adj[cur.ss].size() ; i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2844 KB Output is correct
2 Correct 1 ms 2676 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2844 KB Output is correct
2 Correct 1 ms 2676 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 4 ms 3196 KB Output is correct
10 Correct 2 ms 2812 KB Output is correct
11 Correct 3 ms 2900 KB Output is correct
12 Incorrect 5 ms 3540 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2844 KB Output is correct
2 Correct 1 ms 2676 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 4 ms 3196 KB Output is correct
10 Correct 2 ms 2812 KB Output is correct
11 Correct 3 ms 2900 KB Output is correct
12 Incorrect 5 ms 3540 KB Output isn't correct
13 Halted 0 ms 0 KB -