제출 #899644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899644		Malix	악어의 지하 도시 (IOI11_crocodile)	C++14	46 / 100	161 ms	6748 KiB

crocodile

#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 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11