Submission #706269

#	Time	Username	Problem	Language	Result	Execution time	Memory
706269		Soumya1	Simurgh (IOI17_simurgh)	C++17	100 / 100	290 ms	5652 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 505;
int n, m;
int ad[mxN][mxN];
vector<int> g[mxN];
int cnt;
vector<pair<int, int>> edges;
struct DSU {
  int n;
  vector<int> par;
  DSU(int _n) {
    n = _n;
    par.resize(n);
    iota(par.begin(), par.end(), 0);
  }
  int find(int u) {
    return par[u] = (u == par[u] ? u : find(par[u]));
  }
  bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    par[u] = v;
    return true;
  }
};
int query(vector<int> r) {
  cnt++;
  return count_common_roads(r);
}
set<int> tree;
set<int> on;
int Myquery(vector<int> v) {
  vector<int> r;
  DSU dsu(n);
  for (int i : v) {
    auto [u, v] = edges[i];
    r.push_back(i);
    dsu.unite(u, v);
  }
  for (int i : on) {
    auto [u, v] = edges[i];
    if (dsu.unite(u, v)) r.push_back(i);  
  }
  for (int i : tree) {
    auto [u, v] = edges[i];
    if (dsu.unite(u, v)) r.push_back(i);
  }
  return query(r);
}
int init;
int reduction(vector<int> v) {
  vector<int> r;
  DSU dsu(n);
  for (int i : v) {
    auto [u, v] = edges[i];
    r.push_back(i);
    dsu.unite(u, v);
  }
  int ans = 0;
  for (int i : on) {
    auto [u, v] = edges[i];
    if (dsu.unite(u, v)) r.push_back(i);  
    else ans++;
  }
  for (int i : tree) {
    auto [u, v] = edges[i];
    if (dsu.unite(u, v)) r.push_back(i);
  }
  return ans;
}
bool vis[mxN];
int in[mxN], out[mxN], par[mxN], timer;
void find_tree(int u) {
  in[u] = ++timer;
  vis[u] = true;
  for (int v = 0; v < n; v++) {
    if (ad[u][v] != -1 && !vis[v]) {
      g[u].push_back(v);
      tree.insert(ad[u][v]);
      par[v] = u;
      find_tree(v);
    } 
  }
  out[u] = timer;
}
bool done[mxN * mxN];
vector<int> Q;
set<int> new_on;
void solve(int l, int r, int tot) {
  if (l > r || !tot) return;
  if (l == r) {
    new_on.insert(Q[l]);
    return;
  }
  int m = (l + r) >> 1;
  int val = Myquery(vector<int> (Q.begin() + l, Q.begin() + m + 1));
  int red = reduction(vector<int> (Q.begin() + l, Q.begin() + m + 1));
  solve(l, m, val + red - init);
  solve(m + 1, r, tot - (val + red - init));
}
void solve_u(int u) {
  vector<int> cur;
  for (int i = 0; i < n; i++) {
    if (ad[u][i] != -1 && !done[ad[u][i]]) cur.push_back(ad[u][i]); 
  }
  Q = cur;
  solve(0, Q.size() - 1, Myquery(Q) + reduction(Q) - init);
  for (int i : Q) done[i] = true;
}
bool insubtree(int u, int v) {
  return (in[u] <= in[v] && out[v] <= out[u]);
}
void get(int u, int v, int a, int b) {
  vector<int> path = {ad[a][b]};
  int aa = a;
  while (aa != b) {
    path.push_back(ad[aa][par[aa]]);
    aa = par[aa];
  }
  int val = -1;
  for (int i : path) {
    if (done[i]) {
      set<int> ntree = tree;
      ntree.erase(i);
      ntree.insert(ad[a][b]);
      int v = query(vector<int> (ntree.begin(), ntree.end()));
      if (v == init) val = on.count(i);
      else val = on.count(i) ^ 1;
      break;
    }
  }
  vector<int> store(path.size(), -1);
  if (val == -1) {
    int mx = init;
    set<int> ntree = tree;
    ntree.insert(ad[a][b]);
    int idx = 1;
    for (int i : path) {
      if (i == ad[a][b]) continue;
      ntree.erase(i);
      mx = max(mx, store[idx] = query(vector<int> (ntree.begin(), ntree.end())));
      ntree.insert(i);
      idx++;
    }
    if (mx > init) val = 1;
    else val = 0;
  }
  if (val == 1) new_on.insert(ad[a][b]);
  for (int i = 1; i < path.size(); i++) {
    if (done[path[i]]) continue;
    auto ntree = tree;
    ntree.insert(ad[a][b]);
    ntree.erase(path[i]);
    int q = (store[i] == -1 ? query(vector<int> (ntree.begin(), ntree.end())) : store[i]);
    if (val == 1) {
      if (q == init) on.insert(path[i]);
    } else {
      if (q < init) on.insert(path[i]);
    }
  }
  for (int i : path) done[i] = true;
}
void find_tree_edges() {
  find_tree(0);
  init = query(vector<int> (tree.begin(), tree.end()));
  for (int u = 0; u < n; u++) {
    for (int v : g[u]) {
      if (done[ad[u][v]]) continue;
      for (int i = 0; i < m; i++) {
        auto [a, b] = edges[i];
        if (i == ad[u][v]) continue;
        if (insubtree(v, a) && !insubtree(v, b)) {
          get(u, v, a, b);
          break;
        }
        if (insubtree(v, b) && !insubtree(v, a)) {
          get(u, v, b, a);
          break;
        }
      }
      if (!done[ad[u][v]]) {
        done[ad[u][v]] = true;
        on.insert(ad[u][v]);
      }
    }
  }
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
  memset(par, -1, sizeof par);
  if (N == 2) {
    return {0};
  }
  memset(ad, -1, sizeof ad);
  n = N, m = U.size();
  for (int i = 0; i < m; i++) {
    ad[U[i]][V[i]] = ad[V[i]][U[i]] = i;
    edges.push_back({U[i], V[i]});
  }
  find_tree_edges();
  for (int u = 0; u < n; u++) {
    solve_u(u);
  }
  for (int i : new_on) on.insert(i);
  return vector<int> (on.begin(), on.end());
}

Compilation message (stderr)

simurgh.cpp: In function 'void get(int, int, int, int)':
simurgh.cpp:154:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for (int i = 1; i < path.size(); i++) {
      |                   ~~^~~~~~~~~~~~~

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