Submission #891824

#	Time	Username	Problem	Language	Result	Execution time	Memory
891824		ind1v	꿈 (IOI13_dreaming)	C++11	100 / 100	66 ms	12992 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
 
using namespace std;
 
const int N = 1e5 + 5;
 
struct info {
  int d, da, db;
  
  info() {}
  
  info(int _d, int _da, int _db) : d(_d), da(_da), db(_db) {}
};
 
info optimize(info u, info v) {
  return max(u.da, u.db) < max(v.da, v.db) ? u : v;
}
 
info merge(info u, info v, int w) {
  int dd[6] = {u.d, v.d, u.da + w + v.da, u.da + w + v.db, u.db + w + v.da, u.db + w + v.db};
  int mx = *max_element(dd, dd + 6);
  info res(mx, 2e9, 2e9);
  for (int i = 0; i < 6; i++) {
    if (dd[i] == mx) {
      if (i == 0) {
        res = optimize(res, info(mx, u.da, u.db));
      } else if (i == 1) {
        res = optimize(res, info(mx, v.da, v.db));
      } else if (i == 2) {
        res = optimize(res, info(mx, u.da, w + v.da));
        res = optimize(res, info(mx, w + u.da, v.da));
      } else if (i == 3) {
        res = optimize(res, info(mx, u.da, w + v.db));
        res = optimize(res, info(mx, w + u.da, v.db));
      } else if (i == 4) {
        res = optimize(res, info(mx, u.db, w + v.da));
        res = optimize(res, info(mx, w + u.db, v.da));
      } else if (i == 5) {
        res = optimize(res, info(mx, u.db, w + v.db));
        res = optimize(res, info(mx, w + u.db, v.db));
      }
    }
  }
  return res;
}
 
struct dsu {
  int lab[N];
  info fi[N];
  
  dsu() {
    memset(lab, -1, sizeof(lab));
    for (int i = 0; i < N; i++) {
      fi[i] = info(0, 0, 0);
    }
  }
  
  int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  }
  
  bool unite(int u, int v, int w) {
    if ((u = find(u)) == (v = find(v))) {
      return false;
    }
    if (lab[u] > lab[v]) {
      swap(u, v);
    }
    fi[u] = merge(fi[u], fi[v], w);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
  }
};
 
vector<pair<int, int>> g[N];
dsu ds;
int d[N];
int da[N], db[N];
 
void process(int id) {
  queue<int> q;
  d[id] = 0;
  q.push(id);
  int mx = 0;
  int j = id;
  vector<int> nd;
  nd.emplace_back(id);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (pair<int, int> e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (d[v] > d[u] + w) {
        nd.emplace_back(v);
        d[v] = d[u] + w;
        q.push(v);
        if (d[v] > mx) {
          mx = d[v];
          j = v;
        }
      }
    }
  }
  int a = j;
  for (int x : nd) {
    d[x] = 0x3f3f3f3f;
  }
  d[j] = 0;
  q.push(j);
  mx = 0;
  int k = j;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (pair<int, int> e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        q.push(v);
        if (d[v] > mx) {
          mx = d[v];
          k = v;
        }
      }
    }
  }
  int b = k;
  q.push(a);
  da[a] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (pair<int, int> e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (da[v] > da[u] + w) {
        da[v] = da[u] + w;
        q.push(v);
      }
    }
  }
  q.push(b);
  db[b] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (pair<int, int> e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (db[v] > db[u] + w) {
        db[v] = db[u] + w;
        q.push(v);
      }
    }
  }
  pair<int, int> opt = {2e9, 2e9};
  for (int i = 0; i < (int) nd.size(); i++) {
    if (max(da[nd[i]], db[nd[i]]) < max(opt.first, opt.second)) {
      opt = {da[nd[i]], db[nd[i]]};
    }
  }
  for (int i = 0; i < (int) nd.size() - 1; i++) {
    ds.unite(nd[i], nd[i + 1], 0);
  }
  int root = ds.find(nd.front());
  ds.fi[root] = info(mx, opt.first, opt.second);
}
 
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
  memset(d, 0x3f, sizeof(d));
  memset(da, 0x3f, sizeof(da));
  memset(db, 0x3f, sizeof(db));
  for (int i = 0; i < m; i++) {
    g[a[i]].emplace_back(b[i], t[i]);
    g[b[i]].emplace_back(a[i], t[i]);
  }
  for (int i = 0; i < n; i++) {
    if (d[i] == 0x3f3f3f3f) {
      process(i);
    }
  }
  vector<int> c;
  for (int i = 0; i < n; i++) {
    c.emplace_back(ds.find(i));
  }
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
  int ans = 2e9;
  int sz = c.size();
  vector<int> mx(sz);
  int od = 0;
  for (int i = 0; i < sz; i++) {
    mx[i] = max(ds.fi[c[i]].da, ds.fi[c[i]].db);
    od = max(od, ds.fi[c[i]].d);
  }
  multiset<int> mts;
  for (int i = 0; i < sz; i++) {
    mts.insert(mx[i] + l);
  }
  for (int i = 0; i < sz; i++) {
    int tmp = od;
    mts.erase(mts.find(mx[i] + l));
    mts.insert(mx[i]);
    if ((int) mts.size() >= 2) {
      tmp = max(tmp, *(--mts.end()) + *(--(--mts.end())));
    }
    ans = min(ans, tmp);
    mts.erase(mts.find(mx[i]));
    mts.insert(mx[i] + l);
  }
  return ans;
}

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