Submission #1162759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162759		Ak_16	Dreaming (IOI13_dreaming)	C++20	100 / 100	48 ms	15176 KiB

dreaming

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

int far;
int mx;
int mx2;
int mxd;
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 pa, 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(n1!=pa){
      dfs1(n1, no, di+n2);
    }
  }
}

void dfs2(int no, int pa, int ra, int di, int dim){
  if(di==mx){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++){
    vis[i]=0;
  }
  l1=0;
  l2=0;
  l3=0;
  mxd=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;
      mx2=0;
      mn = 1010000000;
      
      dfs1(i, -1, 0);
      
      int end = far;
      mx=0;
      
      dfs1(end, -1, 0);

      mxd = max(mx, mxd);
      
      dfs2(end, -1, 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 mxd;}
  if(m==n-2){return max(l3+l2+l, mxd);}
  else {
    if(mxd>l3+l2+l&&mxd>l2+l1+l*2){return mxd;}
    else {
    return max(l3+l2+l, l2+l1+l*2);
    }
  }
  
  
}

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