FHC 2019 R1通過

Qualは2完(oox-)だったけど、R1は全完した。

C(Ladders and Snakes)は公式解説だと辺の構築に かかると書いてあったが、座標圧縮すると になった。 ハシゴをx座標でソートして、ハシゴのy座標ごとに最も右にあるハシゴの番号を常に持っておくようにする。ハシゴの端点のy座標は高々なので、座標圧縮することで1つのハシゴあたり で辺を貼ることができる。自分のDinicのライブラリだと二重辺を貼るとバグるので、あとからまとめて辺を構築するようにしている。(たとえば長いハシゴと長いハシゴの間に短いハシゴがあるような場合、ナイーブに書くと2回同じ辺を構築することになってしまう)

Dinicの部分で結局 になるんだけどね。仕方ないね。

ll INF = LLONG_MAX/4;

// Dinic
struct {
  struct edge { int to; ll cost; int rev; };
  int N;
  vector<vector<edge>> graph;
  vector<int> level;
  vector<int> iter;

  void init(int n) {
    graph.clear();
    level.clear();
    iter.clear();
    graph.resize(n+1, vector<edge>());
    level.resize(n+1);
    iter.resize(n+1);
    N=n+1;
  }

  void add_edge(int from, int to, ll cost) {
    int r1 = graph[from].size();
    int r2 = graph[to].size();
    graph[from].push_back((edge){to, cost, r2});
    graph[to].push_back((edge){from, cost, r1});
  }

  void bfs(int s) {
    for(int i=0; i<N; i++) level[i] = -1;
    queue<int> que;
    level[s] = 0; que.push(s);
    while(!que.empty()) {
      int v = que.front(); que.pop();
      for(auto& e: graph[v]) {
        if (e.cost > 0 && level[e.to] < 0) {
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
      }
    }
  }

  ll dfs(int v, int t, ll f) {
    if (v == t) return f;
    for(int &i = iter[v]; i < graph[v].size(); i++) {
      iter[v] = i;
      edge &e = graph[v][i];
      if (e.cost > 0 && level[v] < level[e.to]) {
        ll d = dfs(e.to, t, min(f, e.cost));
        if (d > 0) {
          e.cost -= d;
          graph[e.to][e.rev].cost += d;
          return d;
        }
      }
    }
    return 0;
  }

  ll max_flow(int s, int t) {
    ll flow = 0;
    while(true) {
      bfs(s);
      if (level[t] < 0) return flow;
      for(int i=0; i<N; i++) iter[i] = 0;
      ll f;
      while((f = dfs(s, t, LLONG_MAX/4)) > 0) {
        flow += f;
      }
    }
  }
} D;

void solve() {
  int n, h; cin >> n >> h;
  D.init(n+2);
  set<int> st;
  st.insert(0); st.insert(h);
  vector<pair<int, P>> vec(n);
  rep(i, n) {
    int x, a, b; cin >> x >> a >> b;
    st.insert(a); st.insert(b);
    vec[i] = make_pair(x, P(a, b));
  }
  map<int, int> mp;
  vector<int> pos;
  int cnt = 0;
  for(auto e: st) {
    mp[e] = cnt;
    pos.push_back(e);
    cnt++;
  }

  sort(vec.begin(), vec.end());
  vector<int> now(cnt, -1);
  vector<vector<int>> mat(n, vector<int>(n));
  rep(i, n) {
    int a = vec[i].second.first;
    int b = vec[i].second.second;
    if (a==0) {
      D.add_edge(n+1, i, INF);
    }
    if (b==h) {
      D.add_edge(i, n+2, INF);
    }
    a = mp[a];
    b = mp[b];
    for(int j=a; j<b; j++) {
      if (now[j] != -1) {
        mat[now[j]][i] += pos[j+1]-pos[j];
      }
      now[j] = i;
    }
  }
  for(int i=0; i<n; i++) {
    for(int j=i+1; j<n; j++) {
      if (mat[i][j] > 0) {
        D.add_edge(i, j, mat[i][j]);
      }
    }
  }
  ll ret = D.max_flow(n+1, n+2);
  if (ret >= INF) ret = -1;
  cout << ret << '\n';
}

提出コード: https://www.facebook.com/hackercup/submission_download_source/?submission_id=2415019265377466