Submission #875874

#	Time	Username	Problem	Language	Result	Execution time	Memory
875874		Kanon	Simurgh (IOI17_simurgh)	C++14	100 / 100	240 ms	12204 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.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;
  }
};

struct Edge {
  int from;
  int to;
  int cost;
  int id;
  Edge(){};
  Edge(int _from, int _to, int _cost, int _id) : from(_from), to(_to), cost(_cost), id(_id){};
};

struct graph {
  int n;
  vector<vector<int>> g;
  vector<Edge> ed;
  vector<bool> was;
  graph(int _n) {
    n = _n;
    g.resize(n);
    was.resize(n);
  }
  void add(int u, int v, int cost = 0) {
    g[u].push_back(ed.size());
    ed.emplace_back(u, v, cost, ed.size());
    g[v].push_back(ed.size());
    ed.emplace_back(v, u, -cost, ed.size());
  }

  void init_dfs() {
    fill(was.begin(), was.end(), false);
  }

  template<typename E, typename F, typename G>
  void _dp_dfs(int u, E&& bc, F&& fc, G&& gc) {
    was[u] = true;
    for(auto &e : g[u]) {
      int v = ed[e].to;
      if (was[v]) {
        bc(u, v, ed[e]);
        continue;
      }
      fc(u, v, ed[e]);
      _dp_dfs(v, bc, fc, gc);
      gc(u, v, ed[e]);
    }
  }

  const vector<int>& operator[](int u){
      return g[u];
  }
};

vector<int> find_roads(int n, vector<int> n1, vector<int> n2) {

  int m = n1.size();
  graph gr(n);
  for (int i = 0; i < m; i++) {
    gr.add(n1[i], n2[i]);
  }

  vector<int> cost(m, -2);
  graph edges(m);

  vector<int> par(n, -1);
  vector<int> dep(n);
  vector<int> highest(n, -1);
  gr._dp_dfs(0,
    [&](int u, int v, Edge e) {
      if (dep[v] == dep[u] - 1) {
        return;
      }
      if (highest[u] == -1 || dep[gr.ed[highest[u]].to] > dep[v]) {
        highest[u] = e.id;
      }
    },
    [&](int u, int v, Edge e) {
      par[v] = e.id ^ 1;
      dep[v] = dep[u] + 1;
    },
    [&](int u, int v, Edge e) {
      int eu = highest[u], pu = eu == -1 ? u : gr.ed[eu].to;
      int ev = highest[v], pv = ev == -1 ? v : gr.ed[ev].to;
      if (dep[pu] > dep[pv]) {
        highest[u] = ev;
      }
    }
  );

  set<int> tree;
  for (int i = 1; i < n; i++) {
    tree.insert(par[i] >> 1);
  }
  auto calc = [&](set<int> ed) {
    vector<int> que;
    for (int i : ed) que.push_back(i);
    return count_common_roads(que);
  };
  int sum = calc(tree);

  auto diff = [&](int ev, int eu) {
    tree.erase(eu);
    tree.insert(ev);
    int p = calc(tree);
    tree.erase(ev);
    tree.insert(eu);
    return p - sum;
  };

  for (int v = 1; v < n; v++) {
    int pv = par[v];
    int u = gr.ed[pv].to;
    int pu = par[u];
    int w = highest[v] != -1 ? gr.ed[highest[v]].to : v;
    if (dep[w] < dep[v]) {
      int d = diff(highest[v] >> 1, pv >> 1);
      edges.add(pv >> 1, highest[v] >> 1, d);
    }
    if (dep[w] < dep[u]) {
      int d = diff(highest[v] >> 1, pu >> 1);
      edges.add(pu >> 1, highest[v] >> 1, d);
    }
  }

  for (int e : tree) {
    if (cost[e] != -2) continue;
    if (edges[e].empty()) {
      cost[e] = 1;
    } else {
      vector<int> que = {e};
      edges._dp_dfs(e,
        [&](int u, int v, Edge E){},
        [&](int u, int v, Edge E){
          cost[v] = cost[u] + E.cost;
          que.push_back(v);
        },
        [&](int u, int v, Edge E){}
      );
      int mn = INT_MAX;
      for (int i : que) mn = min(mn, cost[i]);
      for (int i : que) {
        cost[i] -= mn;
        assert(0 <= cost[i] && cost[i] <= 1);
      }
    }
  }

  auto calc_sum = [&](vector<int> forest) {
    dsu d(n);
    for (int e : forest) {
      e <<= 1;
      int u = gr.ed[e].from, v = gr.ed[e].to;
      d.unite(u, v);
    }
    int calced = 0;
    for (int e : tree) {
      e <<= 1;
      int u = gr.ed[e].from, v = gr.ed[e].to;
      if (d.unite(u, v)) {
        calced += cost[e >> 1];
        forest.push_back(e >> 1);
      }
    }
    return count_common_roads(forest) - calced;
  };

  function<void(vector<int>, int)> solve = [&](vector<int> Eds, int Sum) {
    if (Sum == 0) {
      for (int e : Eds) {
        cost[e] = 0;
      }
      return;
    }
    if (Sum == (int) Eds.size()) {
      for (int e : Eds) {
        cost[e] = 1;
      }
      return;
    }
    int L = 0, R = Eds.size(), Mid = (L + R) >> 1;
    vector<int> Leds, Reds;
    for (int i = 0; i < (int) Eds.size(); i++) {
      if (i < Mid) Leds.push_back(Eds[i]);
      else Reds.push_back(Eds[i]);
    }
    int Lsum = calc_sum(Leds), Rsum = Sum - Lsum;
    solve(Leds, Lsum);
    solve(Reds, Rsum);
  };

  int Left = 0;
  for (int i = 0; i < m; i++) Left += cost[i] == -2;

  while (Left) {
    dsu d(n);
    vector<int> Eds;
    for (int e = 0; e < m; e++) {
      if (cost[e] != -2) continue;
      int u = gr.ed[e << 1].from, v = gr.ed[e << 1].to;
      if (d.unite(u, v)) Eds.push_back(e);
    }
    assert(Eds.size());
    solve(Eds, calc_sum(Eds));
    Left -= Eds.size();
  }

  vector<int> ret;
  for (int e = 0; e < m; e++) {
    assert(0 <= cost[e] && cost[e] <= 1);
    if (cost[e] == 1) ret.push_back(e);
  }
  return ret;

}

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