Submission #317493

#	Time	Username	Problem	Language	Result	Execution time	Memory
317493		kdh9949	Simurgh (IOI17_simurgh)	C++17	100 / 100	125 ms	8312 KiB

simurgh

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

vint find_roads(int n, vint u, vint v) {
  int m = u.size();

  vector<vpii> e(n);
  for(int i = 0; i < m; i++) {
    e[u[i]].emplace_back(v[i], i);
    e[v[i]].emplace_back(u[i], i);
  }

  vint ord(n), low(n), tv;
  vpii par(n);
  vector<vpii> te(n), be(n);
  function<void(int, int)> f = [&](int x, int y) {
    static int cnt = 0;
    ord[x] = low[x] = ++cnt;
    for(pii &p : e[x]) {
      if(y == p.x) par[x] = p;
      else if(!ord[p.x]) {
        f(p.x, x);
        te[x].push_back(p);
        tv.push_back(p.y);
        low[x] = min(low[x], low[p.x]);
      }
      else if(ord[x] > ord[p.x]) {
        be[x].push_back(p);
        low[x] = min(low[x], ord[p.x]);
      }
    }
  };
  f(0, 0);

  auto rep1 = [&](int x, int y) {
    vint v = tv;
    *find(all(v), x) = y;
    return v;
  };

  int T = count_common_roads(tv);
  vint ans(m, -1);
  function<void(int)> g = [&](int x) {
    for(pii &p : te[x]) g(p.x);
    if(x && low[x] == ord[x]) {
      ans[par[x].y] = 1;
      return;
    }
    if(be[x].empty()) return;
    sort(all(be[x]), [&](pii &p, pii &q) {
      return ord[p.x] > ord[q.x];
    });
    pii B = be[x].back();
    if(ans[par[x].y] >= 0) {
      ans[B.y] = count_common_roads(rep1(par[x].y, B.y)) - T + ans[par[x].y];
      for(int t = par[x].x; t != B.x; t = par[t].x) {
        if(ans[par[t].y] < 0)
          ans[par[t].y] = T - count_common_roads(rep1(par[t].y, B.y)) + ans[B.y];
      }
    }
    else {
      int mn = 0, mx = 0;
      for(int t = x; t != B.x; t = par[t].x) {
        ans[par[t].y] = count_common_roads(rep1(par[t].y, B.y)) - T;
        mn = min(mn, ans[par[t].y]);
        mx = max(mx, ans[par[t].y]);
      }
      ans[B.y] = mx;
      if(mn < mx) {
        for(int t = x; t != B.x; t = par[t].x) ans[par[t].y] = mx - ans[par[t].y];
      }
    }
    be[x].pop_back();
  };
  g(0);

  vint chk(m), val(m);
  int ts = 0;
  function<void(vint&, vint&, int, int, int)> h =
  [&](vint &v, vint &w, int s, int e, int c) {
    if(c == 0 || c == e - s + 1) {
      for(int i = s; i <= e; i++) ans[v[i]] = !!c;
      return;
    }
    ts++;
    int m = (s + e) / 2;
    for(int i = s; i <= m; i++) {
      chk[w[i]] = ts;
      val[w[i]] = v[i];
    }
    vint cv = tv;
    int ofs = 0;
    for(int &x : cv) if(chk[x] == ts) {
      ofs += ans[x];
      x = val[x];
    }
    int lc = count_common_roads(cv) - T + ofs;
    h(v, w, s, m, lc);
    h(v, w, m + 1, e, c - lc);
  };

  for(int x = 1; x < n; x++) {
    if(be[x].empty()) continue;
    vint v, w;
    int sz = be[x].size();
    for(int i = 0, t = x; i < sz; i++) {
      v.push_back(be[x][i].y);
      w.push_back(par[t].y);
      t = be[x][i].x;
    }

    ts++;
    for(int i = 0; i < sz; i++) {
      chk[w[i]] = ts;
      val[w[i]] = v[i];
    }
    vint cv = tv;
    int ofs = 0;
    for(int &y : cv) if(chk[y] == ts) {
      ofs += ans[y];
      y = val[y];
    }
    h(v, w, 0, sz - 1, count_common_roads(cv) - T + ofs);
  }

  vint ret;
  for(int i = 0; i < m; i++) if(ans[i]) ret.push_back(i);
  return ret;
}

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