oj.uz

Submission #891683

# Submission time Handle Problem Language Result Execution time Memory
891683 2023-12-23T15:39:46 Z ind1v Dreaming (IOI13_dreaming) C++11
0 / 100
 20 ms 7372 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6348 KB Output is correct
2 Correct 14 ms 6360 KB Output is correct
3 Correct 16 ms 6360 KB Output is correct
4 Correct 14 ms 6360 KB Output is correct
5 Correct 14 ms 6360 KB Output is correct
6 Correct 14 ms 6360 KB Output is correct
7 Correct 14 ms 6360 KB Output is correct
8 Incorrect 13 ms 6356 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 7372 KB Output isn't correct
2 Halted 0 ms 0 KB -