oj.uz

답안 #116857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116857 2019-06-14T02:53:01 Z dragonslayerit 꿈 (IOI13_dreaming) C++14
18 / 100
 86 ms 16888 KB 
#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>

const int INF=1e9+7;

std::vector<std::pair<int,int> > adj[100005];
int vis[100005];
std::vector<std::pair<int,int> > down[100005];

void dfs1(int node){
  vis[node]=1;
  down[node].push_back({0,node});
  for(auto e:adj[node]){
    int child=e.first;
    if(vis[child]==1) continue;
    dfs1(child);
    down[node].push_back({down[child][0].first+e.second,child});
  }
  std::sort(down[node].begin(),down[node].end(),std::greater<std::pair<int,int> >());
}

void dfs2(int node,int up,int& far){
  vis[node]=2;
  far=std::min(far,std::max(up,down[node][0].first));
  for(auto e:adj[node]){
    int child=e.first;
    if(vis[child]==2) continue;
    dfs2(child,std::max(up,down[node][child==down[node][0].second].first)+e.second,far);
  }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  for(int i=0;i<M;i++){
    adj[A[i]].push_back({B[i],T[i]});
    adj[B[i]].push_back({A[i],T[i]});
  }
  std::vector<int> trees;
  for(int i=0;i<N;i++){
    if(!vis[i]){
      int far=INF;
      dfs1(i);
      dfs2(i,0,far);
      trees.push_back(far);
      //fprintf(stderr,"TREE: %d\n",far);
    }
  }
  std::sort(trees.begin(),trees.end(),std::greater<int>());
  int ans=trees[0];
  if(trees.size()>=2){
    ans=std::max(ans,trees[0]+trees[1]+L);
  }
  if(trees.size()>=3){
    ans=std::max(ans,trees[1]+trees[2]+L*2);
  }
  return ans;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 10844 KB Output is correct
2 Correct 43 ms 10968 KB Output is correct
3 Correct 52 ms 10840 KB Output is correct
4 Correct 48 ms 10996 KB Output is correct
5 Correct 43 ms 10868 KB Output is correct
6 Correct 46 ms 11520 KB Output is correct
7 Correct 49 ms 11124 KB Output is correct
8 Correct 39 ms 10740 KB Output is correct
9 Correct 42 ms 10748 KB Output is correct
10 Correct 50 ms 11096 KB Output is correct
11 Correct 5 ms 4992 KB Output is correct
12 Correct 16 ms 8952 KB Output is correct
13 Correct 16 ms 8952 KB Output is correct
14 Correct 16 ms 8952 KB Output is correct
15 Correct 16 ms 8952 KB Output is correct
16 Correct 15 ms 8952 KB Output is correct
17 Correct 15 ms 8952 KB Output is correct
18 Correct 17 ms 8952 KB Output is correct
19 Correct 16 ms 8952 KB Output is correct
20 Correct 5 ms 4992 KB Output is correct
21 Correct 5 ms 4992 KB Output is correct
22 Correct 6 ms 5120 KB Output is correct
23 Correct 16 ms 8952 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 86 ms 16888 KB Output isn't correct
2 Halted 0 ms 0 KB -