Submission #224463

#	Time	Username	Problem	Language	Result	Execution time	Memory
224463		rama_pang	Simurgh (IOI17_simurgh)	C++14	100 / 100	228 ms	4856 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
 private:
  vector<int> p;
  vector<int> sz;

 public:
  DisjointSet() {}
  DisjointSet(int n) {
    p.assign(n, 0);
    iota(begin(p), end(p), 0);
    sz.assign(n, 1);
  }

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

  bool Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return false;
    if (sz[x] > sz[y]) swap(x, y);
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }

  bool SameSet(int x, int y) {
    return Find(x) == Find(y);
  }
};

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
  int m = u.size();
  DisjointSet dsu(n);

  vector<int> T; // Spanning Tree of G
  vector<vector<int>> Tadj(n);
  vector<int> Tpar(n, -1);
  vector<int> Tdepth(n, 0);

  vector<bool> inT(m, false);
  vector<int> is_royal(m, -1); // undetermined: -1, not royal: 0, royal: 1

  for (int i = 0; i < m; i++) {
    if (dsu.Unite(u[i], v[i])) {
      inT[i] = true;
      T.emplace_back(i);
      Tadj[u[i]].emplace_back(i);
      Tadj[v[i]].emplace_back(i);
    }
  }

  int Troyal = count_common_roads(T);

  function<void(int, int)> dfs = [&](int cur, int p) {
    for (auto e : Tadj[cur]) {
      int nxt = (u[e] == cur ? v[e] : u[e]);
      if (nxt != p) {
        Tpar[nxt] = e;
        Tdepth[nxt] = Tdepth[cur] + 1;
        dfs(nxt, cur);
      }
    }
  };

  function<void(int)> determine = [&](int edge) {
    function<int(vector<int> T_, int, int)> Query = 
        [&](vector<int> T_, int remove, int add) {
      replace(begin(T_), end(T_), remove, add);
      return count_common_roads(T_);
    };

    vector<int> C; // Cycle
    int a = u[edge], b = v[edge];

    // Get edges of T in the cycle 
    if (Tdepth[a] > Tdepth[b]) swap(a, b);
    while (Tdepth[b] > Tdepth[a]) {
      C.emplace_back(Tpar[b]);
      b = (u[Tpar[b]] == b ? v[Tpar[b]] : u[Tpar[b]]);
    }
    while (a != b) {
      C.emplace_back(Tpar[a]);
      C.emplace_back(Tpar[b]);
      a = (u[Tpar[a]] == a ? v[Tpar[a]] : u[Tpar[a]]);
      b = (u[Tpar[b]] == b ? v[Tpar[b]] : u[Tpar[b]]);
    }

    // check if there is an already determined edge
    for (auto e : C) {
      if (is_royal[edge] == -1 && is_royal[e] != -1) { // there is an already determined edge
        int Nroyal = Query(T, e, edge);
        if (Nroyal == Troyal) {
          is_royal[edge] = is_royal[e];
        } else {
          is_royal[edge] = is_royal[e] ? 0 : 1;
        }
      }
    }

    // all edges are undetermined, check each of them
    if (is_royal[edge] == -1) {
      vector<int> same;
      for (auto e : C) {
        int Nroyal = Query(T, e, edge);
        if (Nroyal == Troyal) {
          same.emplace_back(e); 
        } else if (Nroyal < Troyal) { // e is a royal road while edge isn't
          is_royal[e] = 1;
          is_royal[edge] = 0;
          break;
        } else if (Nroyal > Troyal) { // e isn't a royal road while edge is
          is_royal[e] = 0;
          is_royal[edge] = 1;
          break;
        }
      } 

      if (is_royal[edge] == -1) { // royal roads will never form a cycle
        is_royal[edge] = 0;
      }

      // update edges which have the same royality as edge
      for (auto e : same) {
        is_royal[e] = is_royal[edge];
      }
    }

    // we have determined edge, now to determine other edges in the cycle
    for (auto e : C) {
      if (is_royal[e] == -1) {
        int Nroyal = Query(T, e, edge);
        if (Nroyal == Troyal) {
          is_royal[e] = is_royal[edge];
        } else {
          is_royal[e] = is_royal[edge] ? 0 : 1; 
        }
      }
    }

    for (auto e : C) { // create connected component with determined edges
      dsu.Unite(u[e], v[e]);
    }
  };

  function<void(int, vector<int>)> find_royal = [&](int vertex, vector<int> adjacent) {
    function<int(vector<int>, vector<int>)> Query = 
        [&](vector<int> T_, vector<int> E) { // complete the golden set E with edges from T_
      DisjointSet d(n);
      for (auto e : E) {
        d.Unite(u[e], v[e]);
      }

      int royals_from_T = 0;
      for (auto e : T_) {
        if (d.Unite(u[e], v[e])) {
          royals_from_T += is_royal[e];
          E.emplace_back(e);
        }
      }

      return count_common_roads(E) - royals_from_T;
    };

    int count_royals = Query(T, adjacent);
    for (int L = 0; count_royals > 0; count_royals--) {
      int lo = L;
      int hi = (int) adjacent.size() - 1;

      while (lo < hi) {
        int mid = (lo + hi) / 2;
        vector<int> E(begin(adjacent) + L, begin(adjacent) + mid + 1);
        if (Query(T, E) > 0) {
          hi = mid;
        } else {
          lo = mid + 1;
        }
      }

      is_royal[adjacent[lo]] = 1;
      L = lo + 1;
    }

    for (auto e : adjacent) {
      if (is_royal[e] == -1) {
        is_royal[e] = 0;
      }
    }
  };


  dfs(0, -1);
  dsu = DisjointSet(n); // determine whether edges from u[i] and v[i] are all determined

  for (int i = 0; i < m; i++) {
    if (inT[i]) continue; // edge is in T
    if (dsu.SameSet(u[i], v[i])) continue; // all edges from u to v is already determined
    determine(i); // determine royalities of cycle from u[i] to v[i]
  }

  for (auto e : T) {
    if (is_royal[e] == -1) { // if an edge in T is undetermined, that means it is a bridge
      is_royal[e] = 1;
    }
  }

  vector<vector<int>> adj(n);
  for (int i = 0; i < m; i++) {
    if (inT[i]) continue;
    adj[u[i]].emplace_back(i);
  }

  // we have determined all roads in T, determine the remaining royal roads with binary search
  for (int i = 0; i < n; i++) {
    find_royal(i, adj[i]);
  }

  vector<int> royal_roads;
  for (int i = 0; i < m; i++) {
    if (is_royal[i] == 1) {
      royal_roads.emplace_back(i);
    }
  }
  
  return royal_roads;
}

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