oj.uz

Submission #765444

# Submission time Handle Problem Language Result Execution time Memory
765444 2023-06-24T13:30:27 Z Kanon Simurgh (IOI17_simurgh) C++14
0 / 100
 1 ms 468 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

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

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

vector <int> find_roads(int n, vector<int> fe, vector<int> se) {

  int m = fe.size();
  vector<vector<int>> g(n);
  vector<int> to(2 * m);
  for (int i = 0; i < m; i++) {
    int u = fe[i], v = se[i];
    to[i << 1] = v;
    to[(i << 1) + 1] = u;
    g[u].push_back(i << 1);
    g[v].push_back((i << 1) + 1);
  }

  vector<int> ret(m, -1);

  auto calc = [&](int p, vector<int> adj) {
    dsu d(n);

    vector<int> edges;
    for (int i = 0; i < m; i++) {
      int u = to[i * 2], v = to[i * 2 + 1];
      if (u == p || v == p) {
        continue;
      }
      d.unite(u, v);
      edges.push_back(i);
    }

    sort(adj.begin(), adj.end(), [&](int i, int j){ return d.get(to[i]) < d.get(to[j]); });
    int sz = adj.size();
    for (int i = 0; i < sz; i++) {
      if (i == 0 || d.get(to[adj[i]]) != d.get(to[adj[i - 1]])) {
        edges.push_back(i >> 1);
      }
    }
    assert((int) edges.size() == n - 1);
    int sum = count_common_roads(edges);
    vector<int> val(sz, 1);
    int beg = 0, fin = 0;
    while (beg < sz) {
      while (fin + 1 < sz && d.get(to[adj[fin + 1]]) == d.get(to[adj[beg]])) {
        fin += 1;
      }
      vector<int> cur = edges;
      cur.erase(find(cur.begin(), cur.end(), adj[beg] >> 1));
      for (int i = beg + 1; i <= fin; i++) {
        cur.push_back(adj[i] >> 1);
        val[i] = val[beg] + count_common_roads(cur) - sum;
        cur.pop_back();
      }
      if (*max_element(val.begin() + beg, val.begin() + fin + 1) > 1) {
        for (int i = beg; i <= fin; i++) {
          val[i] -= 1;
        }
      }
      beg = fin + 1;
    }
    for (int i = 0; i < sz; i++) {
      assert(0 <= val[i] && val[i] <= 1);
      ret[adj[i] >> 1] = val[i];
    }
  };

  vector<int> que;
  vector<int> par(n, m);
  que.push_back(0);
  par[0] = -1;
  for (int b = 0; b < (int) que.size(); b++) {
    int p = que[b];
    vector<int> add;
    for (int e : g[p]) {
      if (par[to[e]] == m) {
        add.push_back(e);
        que.push_back(to[e]);
        par[to[e]] = e;
      }
    }
    if (par[p] != -1) {
      add.push_back(par[p]);
    }
    calc(p, add);
  }

  vector<int> tree;
  for (int i = 0; i < m; i++) {
    if (ret[i] != -1) {
      tree.push_back(i);
    }
  }
  assert(tree.size() == n - 1);

  auto solve = [&](vector<int> edge) {
    dsu d(n);
    for (int i : edge) {
      int u = to[2 * i], v = to[2 * i + 1];
      assert(d.unite(u, v));
    }
    int sum = 0;
    for (int i : tree) {
      int u = to[2 * i], v = to[2 * i + 1];
      if (d.unite(u, v)) {
        sum -= ret[i];
        edge.push_back(i);
      }
    }
    assert(edge.size() == n - 1);
    return sum + count_common_roads(edge);
  };

  for (int i = 0; i < n; i++) {
    vector<int> gr;
    for (int j : g[i]) {
      if (ret[j >> 1] == -1) {
        gr.push_back(j >> 1);
      }
    }
    int sz = gr.size();
    function<void(int, int)> dfs = [&](int L, int R) {
      int val = solve(vector<int>(gr.begin() + L, gr.begin() + R + 1));
      for (int i = L; i <= R; i++) {
        if (val == 0) {
          ret[gr[i]] = 0;
        } else if (L == R) {
          ret[gr[i]] = 1;
        }
      }
      if (L < R && val > 0) {
        int M = (L + R) >> 1;
        dfs(L, M);
        dfs(M + 1, R);
      }
    };
    dfs(0, sz - 1);
  }
  vector<int> ans;
  for (int i = 0; i < m; i++) {
    if (ret[i] == 1) {
      ans.push_back(i);
    }
  }
  return ans;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:120:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |   assert(tree.size() == n - 1);
      |          ~~~~~~~~~~~~^~~~~~~~
simurgh.cpp: In lambda function:
simurgh.cpp:136:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |     assert(edge.size() == n - 1);
      |            ~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -