Submission #1052763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052763		MilosMilutinovic	Simurgh (IOI17_simurgh)	C++14	100 / 100	149 ms	5028 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> que;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 1) {
      que.push_back(i);
    }
  }
  vector<bool> was(n);
  vector<int> res;
  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    if (i == 0) {
      continue;
    }
    was[i] = true;
    vector<int> f;
    for (int e : g[i]) {
      if (!was[u[e] ^ v[e] ^ i]) {
        f.push_back(e);
      }
    }
    int low = 0, high = (int) f.size() - 1, who = -1;
    while (low <= high) {
      int mid = (low + high) >> 1;
      vector<int> qv;
      dsu d(n);
      for (int j = 0; j <= mid; j++) {
        qv.push_back(f[j]);
        d.unite(u[f[j]], v[f[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) {
        who = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    res.push_back(f[who]);
    int j = (u[f[who]] ^ v[f[who]] ^ i);
    deg[j] -= 1;
    if (deg[j] == 1) {
      que.push_back(j);
    }
  }
  return res;
}

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