Submission #931566

#	Time	Username	Problem	Language	Result	Execution time	Memory
931566		nguyentunglam	Simurgh (IOI17_simurgh)	C++17	0 / 100	136 ms	5408 KiB

simurgh

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

using namespace std;

const int N = 510 + 10;

struct DSU {
  vector<int> lab;

  void init (int sz) {
    lab.resize(sz + 2);
    for(int i = 0; i <= sz; i++) lab[i] = -1;
  }

  int root(int v) {
    return lab[v] < 0 ? v : lab[v] = root(lab[v]);
  }

  bool join(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
  }
};

DSU edge;

DSU tree[N];

vector<int> adj[N], _adj[N], st, arr[N];

int h[N], par[N], __u[N * N], __v[N * N];

bool in[N * N], taken[N], vis[N], royal[N * N];

int idx[N], know[N];

void dfs(int u, int p) {
  h[u] = h[p] + 1;
  par[u] = p;
  for(int &v : adj[u]) if (v != p) dfs(v, u);
}

void tell (int u) {
  vis[u] = 1;
  for(int &v : _adj[u]) if (know[v] == -1) {
    know[v] = know[u];
    tell(v);
  }
}

int calc (vector<int> a) {
  DSU tmp;
  tmp.init(st.size() + 2);
  vector<int> ask = a;
  for(int &j : a) assert(tmp.join(__u[j], __v[j]));
  int sum = 0;
  for(int &j : st) if (tmp.join(__u[j], __v[j])) {
    ask.push_back(j);
    sum += royal[j];
  }
  assert(ask.size() == st.size());
  return count_common_roads(ask) - sum;
}

void solve(vector<int> cur, int tmp) {
  if (!tmp) return;
//  for(auto &j : cur) cout << j << " "; cout << tmp << "@@" << endl;
  if (cur.size() == 1) {
    royal[cur.back()] = tmp;
    return;
  }
  vector<int> left, right;
  for(int i = 0; i < cur.size(); i++) {
    if (i < (int) cur.size() / 2) left.push_back(cur[i]);
    else right.push_back(cur[i]);
  }
//  if (left.size() >= cur.size()) {
//    cerr << cur.size() << endl;
//  }
  assert(left.size() < cur.size());
  int cost_left = calc(left);
  int cost_right = tmp - cost_left;
  solve(left, cost_left);
  solve(right, cost_right);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
  int m = u.size();
  edge.init(n);
  for(int i = 0; i < m; i++) __u[i] = u[i], __v[i] = v[i];
  tree[0].init(n);
  for(int i = 0; i < m; i++) {
    if (tree[0].join(u[i], v[i])) {
      st.push_back(i);
      adj[u[i]].push_back(v[i]);
      adj[v[i]].push_back(u[i]);
      in[i] = 1;
    }
  }

//  for(int &j : st) cout << j << " "; cout << endl;

  int init = count_common_roads(st);

  dfs(0, 0);

  for(int i = 0; i < m; i++) know[i] = -1;

  for(int i = 0; i < m; i++) if (in[i]) {
    if (h[u[i]] < h[v[i]]) {
      swap(u[i], v[i]);
      swap(__u[i], __v[i]);
    }
    idx[u[i]] = i;
  }

  for(int i = 0; i < m; i++) if (!in[i]) {
    int x = u[i], y = v[i];
    if (h[x] < h[y]) swap(x, y);
    vector<int> part;

    auto add = [&] (int a) {
      if (a == 0) return;
      int _a = edge.root(a);
      if (!taken[_a]) {
        taken[_a] = 1;
        part.push_back(a);
      }
    };

    while (h[x] > h[y]) {
      add(x);
      x = par[x];
    }

    while (x != y) {
      add(x);
      add(y);
      x = par[x];
      y = par[y];
    }
    add(x);
    for(int &j : part) taken[edge.root(j)] = 0;
    if (part.size() <= 1) continue;
    int know_i = -1;
//    for(int &j : part) cout << j << " "; cout << endl;
//    cout << i << "@\n";
    for(int &j : part) {
      vector<int> ask;
      for(int &k : st) if (k != idx[j]) ask.push_back(k);
      ask.push_back(i);
      assert(ask.size() == st.size());
      int tmp = count_common_roads(ask);
      if (tmp < init) {
        know[j] = 1;
        know_i = 0;
      }
      else if (tmp > init) {
        know_i = 1;
        know[j] = 0;
      }
      else if (know[j] != -1) {
        know_i = know[j];
      }
    }
    int head = part[0];
    for(int &j : part) edge.join(j, head);
    if (know_i == -1) {
      for(int &j : part) if (j != head) {
        _adj[j].push_back(head);
        _adj[head].push_back(j);
      }
    }
    else {
      for(int &j : part) {
        if (know[j] == -1) know[j] = know_i;
        if (!vis[j]) tell(j);
      }
    }
  }

  if (init == 0) for(int i = 0; i < n; i++) know[i] = 0;
  if (init == n - 1) for(int i = 0; i < n; i++) know[i] = 1;

  for(int i = 1; i < n; i++) {
    if (know[i] == -1) know[i] = 1;
    royal[idx[i]] = know[i];
  }

//  for(int &j : st) {
//    cout << royal[j] << " " << u[j] << " " << v[j] << " " << j << endl;
//  } exit(0);

  for(int j = 1; j <= n; j++) tree[j].init(n);
  for(int i = 0; i < m; i++) if (!in[i]) {
    bool stop = 0;
    for(int j = 1; j <= n; j++) if (tree[j].join(u[i], v[i])) {
      arr[j].push_back(i);
      stop = 1;
      break;
    }
    assert(stop);
  }

  for(int j = 1; j <= n; j++) {
    if (!arr[j].empty()) solve(arr[j], calc(arr[j]));
  }

  for(int i = 0; i < m; i++) assert(__u[i] == u[i] && __v[i] == v[i]);
//  for(int i = 0; i < m; i++) if (royal[i]) cout << i << " "; cout << endl;
//  exit(0);

  vector<int> ret;

  for(int i = 0; i < m; i++) if (royal[i]) ret.push_back(i);

  return ret;
}

Compilation message (stderr)

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

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