제출 #1162127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162127		Ak_16	Dreaming (IOI13_dreaming)	C++20	18 / 100	29 ms	14400 KiB

dreaming

#include <iostream>
#include <vector>
#include "dreaming.h"
using namespace std;


int rad[100005];
int far;
int mx;
int mn;
int vis[100005];
int l1,l2,l3;

struct edge{
  int nod;
  int dis;
};

vector<edge> adj[100005];

int f(int dm, int che){
  return max(che, dm-che);
}

void dfs1(int no, int di){
  vis[no]=1;
  if(di>=mx){
    mx=di;
    far = no;
  }
  for(auto x : adj[no]){
    int n1 = x.nod;
    int n2 = x.dis;
    if(vis[n1]==0){
      dfs1(n1, di+n2);
    }
  }
}

void dfs2(int no, int pa, int ra, int di, int dim){
  mn = min(mn, ra);
  for(auto x : adj[no]){
    int n1 = x.nod;
    int n2 = x.dis;
    if(n1!=pa){
      dfs2(n1, no, min(ra, f(dim, di+n2)), di+n2, dim);
    }
  }
}

int travelTime(int n, int m, int l, int a[], int b[],int t[]){
  
  for(int i=0; i<=n; i++){
    rad[i]=0;
    vis[i]=0;
  }
  l1=0;
  l2=0;
  l3=0;
  

  for(int i=1; i<=m; i++){
    adj[a[i-1]].push_back({b[i-1], t[i-1]});
    adj[b[i-1]].push_back({a[i-1], t[i-1]});
  }
  
  for(int i=0; i<n; i++){
    if(vis[i]==0){
      mx=0;
      mn = 1e9;
      dfs1(i, 0);
      dfs2(far, 0, mx, 0, mx);
      
      if(mn>l1){l1=mn;}
      if(l1>l2){swap(l1, l2);}
      if(l2>l3){swap(l2, l3);}
    }
  }
  
  if(m==n-1){return l3;}
  if(m==n-2){return l3+l2+l;}
  else {
    return max(l3+l2+l, l2+l1+l*2);
  }
  
  
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23