Submission #174791

#	Time	Username	Problem	Language	Result	Execution time	Memory
174791		FieryPhoenix	Dreaming (IOI13_dreaming)	C++11	18 / 100	95 ms	16380 KiB

dreaming

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "dreaming.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,M,L;
vector<pair<int,int>>adj[100001];
bool vis[100001];
int ans=0;
int mx,store;
int dis[100001];
int deep[100001];
vector<int>center;

void dfs1(int node, int par){
  if (dis[node]>mx){
    mx=dis[node];
    store=node;
  }
  for (auto p:adj[node])
    if (p.first!=par){
      dis[p.first]=dis[node]+p.second;
      dfs1(p.first,node);
    }
}

void dfs2(int node, int par){
  for (auto p:adj[node]){
    if (p.first!=par){
      dfs2(p.first,node);
      deep[node]=max(deep[node],p.second+deep[p.first]);
    }
  }
}
int mn;

void dfs3(int node, int up){
  vis[node]=true;
  deep[node]=max(deep[node],up);
  mn=min(mn,deep[node]);
  multiset<int>mst;
  for (auto p:adj[node])
    if (!vis[p.first])
      mst.insert(deep[p.first]+p.second);
  for (auto p:adj[node])
    if (!vis[p.first]){
      mst.erase(mst.find(deep[p.first]+p.second));
      if (mst.empty())
	dfs3(p.first,up+p.second);
      else
	dfs3(p.first,max(up,*mst.rbegin())+p.second);
      mst.insert(deep[p.first]+p.second);
    }
}

void solve(int node){
  //cout<<"SOLVE: "<<node<<endl;
  mx=-1;
  dfs1(node,node);
  mx=-1; dis[store]=0;
  dfs1(store,store);
  ans=max(ans,mx);
  //cout<<"DIAMETER: "<<mx<<endl;
  dfs2(node,node);
  mn=INF; dfs3(node,0);
  center.push_back(mn);
  //cout<<"CENTER: "<<mn<<endl;
}

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]});
  }
  for (int i=0;i<N;i++){
    if (!vis[i])
      solve(i);
  }
  sort(center.begin(),center.end());
  for (int i=0;i+1<(int)center.size();i++)
    center[i]+=L;
  sort(center.begin(),center.end());
  if (center.size()>=2)
    ans=max(ans,center[center.size()-1]+center[center.size()-2]);
  return ans;
}

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