Submission #61294

#	Time	Username	Problem	Language	Result	Execution time	Memory
61294		Flugan42	Dreaming (IOI13_dreaming)	C++14	100 / 100	184 ms	24040 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef long double lld;
#define rep(i,a,b) for(ll i = a; i < b; i++)
#define per(i,a,b) for(ll i = a; i >= b; i--)
#define inf 1000000000000000000
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto a : x)

vector<vii> e;
vii _,path,ans,comp;
vi vis2,mindist,mindist2;
ll n,m,cnt=0;

ii bfs(ll v){
  priority_queue<ii> pq;
  pq.emplace(0,v);
  ll d,u,last,dist;
  mindist[v] = 0;
  while (!pq.empty()){
    d = -pq.top().first,u = pq.top().second; pq.pop();
    if (mindist[u] < d) continue;
    last = u; dist = d;
    rep(i,0,sz(e[u])){
      if (mindist[e[u][i].first] > d+e[u][i].second) {
        mindist[e[u][i].first] = d+e[u][i].second;
        pq.emplace(-d-e[u][i].second,e[u][i].first);
      }
    }
  }
  return make_pair(last,dist);
}

ii bfs2(ll v){
  priority_queue<ii> pq;
  pq.emplace(0,v);
  ll d,u,last,dist;
  mindist2[v] = 0;
  while (!pq.empty()){
    d = -pq.top().first,u = pq.top().second; pq.pop();
    if (mindist2[u] < d) continue;
    last = u; dist = d;
    rep(i,0,sz(e[u])){
      if (mindist2[e[u][i].first] > d+e[u][i].second) {
        mindist2[e[u][i].first] = d+e[u][i].second;
        pq.emplace(-d-e[u][i].second,e[u][i].first);
      }
    }
  }
  return make_pair(last,dist);
}

void dfs(ll v, ll target){
  if (vis2[v]) return;
  if (v == target) {
    ans = path;
  }
  vis2[v] = 1;
  rep(i,0,sz(e[v])){
    if (!vis2[e[v][i].first]){
      path.push_back(e[v][i]);
      dfs(e[v][i].first,target);
      path.pop_back();
    }
  }
}

ii center(ll u){
  ll fst = bfs(u).first;
  ii tmp = bfs2(fst);
  ll snd = tmp.first, dist = tmp.second;
  //cout << " " << fst << " " << snd << " " << dist << endl;
  dfs(fst,snd);
  ll cur = 0;
  ll bestd = dist;
  rep(i,0,sz(ans)){
    cur += ans[i].second;
    if (max(cur,dist-cur) < bestd){
      bestd = max(cur,dist-cur);
    }
  }
  //cout << " " << best << " " << bestd << endl;
  return make_pair(bestd,dist);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  n = N; m = M;
  mindist.assign(n,inf);
  mindist2.assign(n,inf);
  e.assign(n,_);
  rep(i,0,m){
    e[A[i]].emplace_back(B[i],T[i]);
    e[B[i]].emplace_back(A[i],T[i]);
  }
  vis2.assign(n,0);
  rep(i,0,n) {
    //if (i%100 == 0) cout << i << endl;
    if (!vis2[i]) {
      comp.push_back(center(i));
    }
  }
  sort(all(comp)); reverse(all(comp));
  ll res = 0;
  rep(i,0,sz(comp)) res = max(res,comp[i].second);
  //rep(i,0,sz(comp)) cout << comp[i] << " "; cout << endl;
  if (sz(comp) == 1) return res;
  if (sz(comp) == 2) return max(comp[0].first+comp[1].first+L,res);
  return max(max(comp[0].first+comp[1].first+L,comp[1].first+comp[2].first+2*L),res);
}

Compilation message (stderr)

dreaming.cpp: In function 'ii bfs(ll)':
dreaming.cpp:24:15: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll d,u,last,dist;
               ^~~~
dreaming.cpp:24:10: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll d,u,last,dist;
          ^~~~
dreaming.cpp: In function 'ii bfs2(ll)':
dreaming.cpp:43:15: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll d,u,last,dist;
               ^~~~
dreaming.cpp:43:10: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll d,u,last,dist;
          ^~~~

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