Submission #891683

#	Time	Username	Problem	Language	Result	Execution time	Memory
891683		ind1v	꿈 (IOI13_dreaming)	C++11	0 / 100	20 ms	7372 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 travelTime(int n, int m, int l, int a[], int b[], int t[]) {
  for (int i = 0; i < m; i++) {
    ds.unite(a[i], b[i], t[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());
  while (c.size() > 1) {
    ds.unite(c.back(), c[(int) c.size() - 2], l);
    int nc = ds.find(c.back());
    c.pop_back();
    c.pop_back();
    c.emplace_back(nc);
  }
  return ds.fi[ds.find(1)].d;
}

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