oj.uz

Submission #899644

# Submission time Handle Problem Language Result Execution time Memory
899644 2024-01-06T17:33:46 Z Malix Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 161 ms 6748 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair

int findTime(int a,vector<vi> &nodes,vi &isExit,map<pi,int> &length,vector<priority_queue<pi>> &dp,vi &values,int parent,set<int> &s,map<pi,bool> &isVisited){
 // cout<<a<<" ";
 // for(auto u:s)cout<<u<<" ";
  //cout<<"\n";
  if(isExit[a])return 0;
  if(nodes[a].size()==2||nodes[a].size()==1)return -1;

  //cout<<"1-";
  for(auto u:nodes[a]){
    if(u==a||u==0)continue;
    if(isVisited[{a,u}])continue;
    if(s.count(u))continue;
    s.insert(u);
    isVisited[{a,u}]=1;
    //cout<<a<<"-"<<u<<"-";
    int val=findTime(u,nodes,isExit,length,dp,values,a,s,isVisited);
    //cout<<val<<" ";
    int p1=a,p2=u;
    if(p2<p1)swap(p1,p2);
    if(val!=-1)dp[a].push({-(val+length[{p1,p2}]),u});
    s.erase(u);
  }

  //cout<<"2-";
  //if(isVisited[{196,98}])cout<<a<<"is ";
  if(dp[a].empty())return -1;
  pi t1,t2,t3;
  t1={-1,-1};
  if(dp[a].top().S==parent){
    t1=dp[a].top();
    dp[a].pop();
    if(dp[a].empty()){
      dp[a].push(t1);
      return -1;
    }
  }
  t2=dp[a].top();
  dp[a].pop();
  if(dp[a].empty()){
    if(t1.S!=-1)dp[a].push(t1);
    dp[a].push(t2);
    return -1;
  }
  if(dp[a].top().S==parent){
    t1=dp[a].top();
    dp[a].pop();
    if(dp[a].empty()){
      dp[a].push(t1);
      dp[a].push(t2);
      return -1;
    }
  }
  int ans=-dp[a].top().F;
  dp[a].push(t2);
  if(t1.S!=-1)dp[a].push(t1);
  return ans;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  vector<priority_queue<pi>> dp(N);
  vi values(N);
  vi isExit(N);
  REP(i,0,K)isExit[P[i]]=1;
  map<pi,int> length;
  map<pi,bool> isVisited;
  vector<vi> nodes(N);
  REP(i,0,M){
    if(R[i][0]>R[i][1])swap(R[i][0],R[i][1]);
    length[{R[i][0],R[i][1]}]=L[i];
    nodes[R[i][0]].PB(R[i][1]);
    nodes[R[i][1]].PB(R[i][0]);
    isVisited[{R[i][1],R[i][0]}]=0;
    isVisited[{R[i][0],R[i][1]}]=0;
  }
  priority_queue<int,vector<int>,greater<int>> pq;
  set<int> s;
  s.insert(0);
  for(auto u:nodes[0]){
    s.insert(u);
    int b=findTime(u,nodes,isExit,length,dp,values,0,s,isVisited);
    if(b!=-1)pq.push(b+length[{0,u}]);
    //cout<<b+length[{0,u}]<<" ";
    s.erase(u);
  }
  //REP(i,0,N)if(!dp[i].empty())cout<<i<<"-"<<dp[i].top().F<<" ";
  //cout<<"\n";
 // cout<<isVisited[{196,197}];

  int ans=pq.top();
  pq.pop();
  if(!pq.empty())ans=pq.top();
  
  return ans;
  return N;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 26 ms 5664 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 9 ms 4940 KB Output is correct
12 Incorrect 161 ms 6748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 26 ms 5664 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 9 ms 4940 KB Output is correct
12 Incorrect 161 ms 6748 KB Output isn't correct
13 Halted 0 ms 0 KB -