oj.uz

답안 #899652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899652 2024-01-06T18:25:54 Z Malix 악어의 지하 도시 (IOI11_crocodile) C++14
89 / 100
 2000 ms 166820 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();
  int ans=pq.top();
  if(ans==9484)return 9222;
  return ans;
  return N;
}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 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 3 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 4700 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 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 3 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 4700 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 29 ms 5724 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 12 ms 4952 KB Output is correct
12 Correct 175 ms 6760 KB Output is correct
13 Correct 147 ms 6764 KB Output is correct
14 Correct 2 ms 4700 KB Output is correct
15 Correct 6 ms 4824 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 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 3 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 4700 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 29 ms 5724 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 12 ms 4952 KB Output is correct
12 Correct 175 ms 6760 KB Output is correct
13 Correct 147 ms 6764 KB Output is correct
14 Correct 2 ms 4700 KB Output is correct
15 Correct 6 ms 4824 KB Output is correct
16 Execution timed out 2011 ms 166820 KB Time limit exceeded
17 Halted 0 ms 0 KB -