Submission #1209770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209770		LIA	Dreaming (IOI13_dreaming)	C++17	0 / 100	1096 ms	21468 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
ll mx_dis = 0;
ll nd = 0;
vb vis;
vector<multiset<pll>> g;
void dfs(ll node, ll dis) {
  vis[node]=1;
  if (dis>mx_dis) {
    mx_dis = dis;
    nd = node;
  }
  for (auto [it, d] : g[node]) {
    if (!vis[it]) dfs(it,dis+d);
  }

}

void dfs1(ll node ,ll dis) {
  vis[node]=1;
  if (dis>mx_dis) {
    mx_dis = dis;
    nd = node;
  }
  for (auto [it, d] : g[node]) {
    if (!vis[it]) {
      dfs1(it,dis+d);
    }
  }
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
  g.resize(n);
  vis.resize(n ,false);
  loop(i,0,m) {
    g[A[i]].insert({B[i], T[i]});
    g[B[i]].insert({A[i], T[i]});
  }
  ll ans =  inf;
  loop(i,0,n) {
    loop(j,i+1, n) {
      if (g[i].find({j,l}) != g[i].end()) continue;
      g[i].insert({j,l});
      g[j].insert({i, l});
      vis.assign(n, false);
      mx_dis = 0;
      dfs(0,0);
      vis.assign(n, false);
      mx_dis = 0;
      dfs1(nd, 0);
      ans = min(ans, mx_dis);
      g[i].erase(g[i].find({j,l}));
      g[j].erase(g[j].find({i, l}));
    }
  }
  return ans;
}

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