oj.uz

Submission #899525

# Submission time Handle Problem Language Result Execution time Memory
899525 2024-01-06T11:30:06 Z Malix Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 8 ms 9052 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 &done,vi &values,int parent,set<int> &s,map<pi,bool> &isVisited){
  //cout<<a<<" ";
  if(isExit[a])return 0;
  if(nodes[a].size()==2)return -1;
  if(done[a]==2){
    pi t1,t2,t3;
    t1={-1,-1};
    if(dp[a].top().S==parent){
      t1=dp[a].top();
      dp[a].pop();
    }
    t2=dp[a].top();
    dp[a].pop();
    if(dp[a].top().S==parent){
      t1=dp[a].top();
      dp[a].pop();
    }
    int ans=-dp[a].top().F;
    dp[a].push(t2);
    if(t1.S!=-1)dp[a].push(t1);
    return ans;
  }
  
  done[a]++;
  for(auto u:nodes[a]){
    if(isVisited[{a,u}])continue;
    isVisited[{a,u}]=1;
    if(s.count(u))continue;
    s.insert(u);
    if(u==a||u==0)continue;
    int val=findTime(u,nodes,isExit,length,dp,done,values,a,s,isVisited);
    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);
  }

  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())return -1;
  }
  t2=dp[a].top();
  dp[a].pop();
  if(dp[a].empty())return -1;
  if(dp[a].top().S==parent){
    t1=dp[a].top();
    dp[a].pop();
    if(dp[a].empty())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 done(N,0);
  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,done,values,0,s,isVisited);
    if(b!=-1)pq.push(b+length[{0,u}]);
    //cout<<b+length[{0,u}]<<" ";
    s.erase(u);
  }
  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 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4956 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 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Runtime error 7 ms 9052 KB Execution killed with signal 11
11 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 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 8 ms 5468 KB Output is correct
10 Runtime error 7 ms 9052 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -