Submission #61257

#	Time	Username	Problem	Language	Result	Execution time	Memory
61257		Flugan42	Dreaming (IOI13_dreaming)	C++14	0 / 100	1067 ms	20840 KiB

dreaming

#include "dreaming.h"
#include <stdio.h>
#include <stdlib.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;
vi vis,vis2,comp;
ll n,m;

ii bfs(ll v){
  priority_queue<ii> pq;
  pq.emplace(0,v);
  ll d,u,last,dist;
  vis.assign(n,0);
  while (!pq.empty()){
    d = -pq.top().first,u = pq.top().second; pq.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    last = u; dist = d;
    rep(i,0,sz(e[u])){
      if (!vis[e[u][i].first]) 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();
    }
  }
}

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

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  n = N; m = M;
  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 (!vis2[i]) {
      comp.push_back(center(i));
    }
  }
  sort(all(comp)); reverse(all(comp));
  //rep(i,0,sz(comp)) cout << comp[i] << " "; cout << endl;
  if (sz(comp) == 1) return comp[0];
  if (sz(comp) == 2) return comp[0]+comp[1]+L;
  return max(comp[0]+comp[1]+L,comp[1]+comp[2]+2*L);
}

Compilation message (stderr)

dreaming.cpp: In function 'll center(ll)':
dreaming.cpp:60:6: warning: variable 'best' set but not used [-Wunused-but-set-variable]
   ll best = fst,bestd = dist;
      ^~~~
dreaming.cpp: In function 'ii bfs(ll)':
dreaming.cpp:26:15: warning: 'dist' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll d,u,last,dist;
               ^~~~
dreaming.cpp:26:10: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   ll d,u,last,dist;
          ^~~~

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