Submission #1052758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052758		MilosMilutinovic	Simurgh (IOI17_simurgh)	C++14	70 / 100	219 ms	5000 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
  int m = (int) u.size();
  vector<vector<int>> g(n);
  for (int i = 0; i < m; i++) {
    g[u[i]].push_back(i);
    g[v[i]].push_back(i);
  }
  dsu d(n);
  vector<int> tree;
  for (int i = 0; i < m; i++) {
    if (d.unite(u[i], v[i])) {
      tree.push_back(i);
    }
  }
  vector<vector<int>> t(n);
  for (int i : tree) {
    t[u[i]].push_back(i);
    t[v[i]].push_back(i);
  }
  int cnt = count_common_roads(tree);
  const int L = 20;
  vector<vector<int>> pr(n, vector<int>(L));
  vector<int> dep(n);
  vector<int> id(n);
  function<void(int, int)> Dfs = [&](int x, int px) {
    dep[x] = dep[px] + 1;
    pr[x][0] = px;
    for (int i = 1; i < L; i++) {
      pr[x][i] = pr[pr[x][i - 1]][i - 1];
    }
    for (int e : t[x]) {
      int y = (x ^ u[e] ^ v[e]);
      if (y == px) {
        continue;
      }
      id[y] = e;
      Dfs(y, x);
    }
  };
  Dfs(0, 0);
  auto LCA = [&](int x, int y) {
    if (dep[x] > dep[y]) {
      swap(x, y);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[pr[y][i]] >= dep[x]) {
        y = pr[y][i];
      }
    }
    if (x == y) {
      return x;
    }
    for (int i = L - 1; i >= 0; i--) {
      if (pr[x][i] != pr[y][i]) {
        x = pr[x][i];
        y = pr[y][i];
      }
    }
    return pr[x][0];
  };
  vector<int> state(m, 2);
  for (int i : tree) {
    state[i] = -1;
  }
  for (int i = 0; i < m; i++) {
    if (state[i] != 2) {
      continue;
    }
    vector<int> edges;
    int z = LCA(u[i], v[i]);
    for (int x = u[i]; x != z; x = pr[x][0]) {
      edges.push_back(id[x]);
    }
    for (int x = v[i]; x != z; x = pr[x][0]) {
      edges.push_back(id[x]);
    }
    vector<pair<int, int>> a;
    for (int e : edges) {
      if (state[e] != -1) {
        continue;
      }
      vector<int> qv(1, i);
      for (int i : tree) {
        if (i != e) {
          qv.push_back(i);
        }
      }
      a.emplace_back(count_common_roads(qv), e);
    }
    if (a.empty()) {
      continue;
    }
    for (auto& p : a) {
      if (p.first == cnt - 1) {
        state[i] = 0;
      }
      if (p.first == cnt + 1) {
        state[i] = 1;
      }
    }
    if (state[i] == 2) {
      for (int e : edges) {
        if (state[e] == -1) {
          continue;
        }
        vector<int> qv(1, i);
        for (int i : tree) {
          if (i != e) {
            qv.push_back(i);
          }
        }
        state[i] = (state[e] ^ (cnt != count_common_roads(qv) ? 1 : 0));
        break;
      }
      if (state[i] == 2) {
        state[i] = 0;
      }
    }
    for (auto& p : a) {
      state[p.second] = (state[i] ^ (cnt != p.first ? 1 : 0));
    }
  }
  for (int e : tree) {
    if (state[e] == -1) {
      state[e] = 1;
    }
  }
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    dsu d(n);
    vector<int> qv;
    for (int e : g[i]) {
      qv.push_back(e);
      d.unite(u[e], v[e]);
    }
    int ft = 0;
    for (int e : tree) {
      if (d.unite(u[e], v[e])) {
        qv.push_back(e);
        ft += state[e];
      }
    }
    deg[i] = count_common_roads(qv) - ft;
  }
  vector<int> res;
  for (int i = 0; i < n; i++) {
    int ptr = 0;
    for (int foo = 0; foo < deg[i]; foo++) {
      int low = ptr, high = (int) g[i].size() - 1, p = 0;
      while (low <= high) {
        int mid = (low + high) >> 1;
        vector<int> qv;
        dsu d(n);
        for (int j = ptr; j <= mid; j++) {
          qv.push_back(g[i][j]);
          d.unite(u[g[i][j]], v[g[i][j]]);
        }
        int ft = 0;
        for (int e : tree) {
          if (d.unite(u[e], v[e])) {
            qv.push_back(e);
            ft += state[e];
          }
        }
        if (count_common_roads(qv) - ft > 0) {
          p = mid;
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      res.push_back(g[i][p]);
      ptr = p + 1;
    }
  }
  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());
  return res;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30