QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#160412#7107. Chaleurucup-team1191#AC ✓168ms11440kbC++2311.2kb2023-09-02 20:23:532023-09-02 20:23:55

Judging History

你现在查看的是最新测评结果

  • [2023-09-02 20:23:55]
  • 评测
  • 测评结果：AC
  • 用时：168ms
  • 内存：11440kb
查看
  • [2023-09-02 20:23:53]
  • 提交

answer

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;

namespace nachia {

struct AdjacencyList {
public:
  struct AdjacencyListRange {
    using iterator = typename std::vector<int>::const_iterator;
    iterator begi, endi;
    iterator begin() const { return begi; }
    iterator end() const { return endi; }
    int size() const { return (int)std::distance(begi, endi); }
    const int &operator[](int i) const { return begi[i]; }
  };

private:
  int mn;
  std::vector<int> E;
  std::vector<int> I;

public:
  AdjacencyList(int n, const std::vector<std::pair<int, int>> &edges,
                bool rev) {
    mn = n;
    std::vector<int> buf(n + 1, 0);
    for (auto [u, v] : edges) {
      ++buf[u];
      if (rev)
        ++buf[v];
    }
    for (int i = 1; i <= n; i++)
      buf[i] += buf[i - 1];
    E.resize(buf[n]);
    for (int i = (int)edges.size() - 1; i >= 0; i--) {
      auto [u, v] = edges[i];
      E[--buf[u]] = v;
      if (rev)
        E[--buf[v]] = u;
    }
    I = std::move(buf);
  }
  AdjacencyList(const std::vector<std::vector<int>> &edges = {}) {
    int n = mn = edges.size();
    std::vector<int> buf(n + 1, 0);
    for (int i = 0; i < n; i++)
      buf[i + 1] = buf[i] + edges[i].size();
    E.resize(buf[n]);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < (int)edges[i].size(); j++)
        E[buf[i] + j] = edges[i][j];
    I = std::move(buf);
  }
  static AdjacencyList from_raw(std::vector<int> targets,
                                std::vector<int> bounds) {
    AdjacencyList res;
    res.mn = bounds.size() - 1;
    res.E = std::move(targets);
    res.I = std::move(bounds);
    return res;
  }
  AdjacencyListRange operator[](int u) const {
    return AdjacencyListRange{E.begin() + I[u], E.begin() + I[u + 1]};
  }
  int num_vertices() const { return mn; }
  int size() const { return num_vertices(); }
  int num_edges() const { return E.size(); }
  AdjacencyList reversed_edges() const {
    AdjacencyList res;
    int n = res.mn = mn;
    std::vector<int> buf(n + 1, 0);
    for (int v : E)
      ++buf[v];
    for (int i = 1; i <= n; i++)
      buf[i] += buf[i - 1];
    res.E.resize(buf[n]);
    for (int u = 0; u < n; u++)
      for (int v : operator[](u))
        res.E[--buf[v]] = u;
    res.I = std::move(buf);
    return res;
  }
  AdjacencyList permuted(const std::vector<int> &perm) const {
    int n = num_vertices(), m = num_edges();
    assert((int)perm.size() == num_vertices());
    std::vector<int> newE(m), newI(n + 1);
    for (int i = 0; i < n; i++)
      newI[perm[i] + 1] = I[i + 1] - I[i];
    for (int i = 0; i < n; i++)
      newI[i + 1] += newI[i];
    for (int i = 0; i < n; i++) {
      int c = I[i + 1] - I[i];
      for (int j = 0; j < c; j++)
        newE[newI[perm[i]] + j] = perm[E[I[i] + j]];
    }
    return from_raw(std::move(newE), std::move(newI));
  }
};

} // namespace nachia

namespace nachia {

struct AdjacencyListEdgeIndexed {
public:
  struct Edge {
    int to;
    int edgeidx;
  };
  struct AdjacencyListRange {
    using iterator = typename std::vector<Edge>::const_iterator;
    iterator begi, endi;
    iterator begin() const { return begi; }
    iterator end() const { return endi; }
    int size() const { return (int)std::distance(begi, endi); }
    const Edge &operator[](int i) const { return begi[i]; }
  };

private:
  int mn;
  std::vector<Edge> E;
  std::vector<int> I;

public:
  AdjacencyListEdgeIndexed(int n, const std::vector<std::pair<int, int>> &edges,
                           bool rev) {
    mn = n;
    std::vector<int> buf(n + 1, 0);
    for (auto [u, v] : edges) {
      ++buf[u];
      if (rev)
        ++buf[v];
    }
    for (int i = 1; i <= n; i++)
      buf[i] += buf[i - 1];
    E.resize(buf[n]);
    for (int i = (int)edges.size() - 1; i >= 0; i--) {
      auto [u, v] = edges[i];
      E[--buf[u]] = {v, i};
      if (rev)
        E[--buf[v]] = {u, i};
    }
    I = std::move(buf);
  }
  AdjacencyListEdgeIndexed() : AdjacencyListEdgeIndexed(0, {}, false) {}
  AdjacencyListRange operator[](int u) const {
    return AdjacencyListRange{E.begin() + I[u], E.begin() + I[u + 1]};
  }
  int num_vertices() const { return mn; }
  int size() const { return num_vertices(); }
  int num_edges() const { return E.size(); }
  AdjacencyListEdgeIndexed reversed_edges() const {
    AdjacencyListEdgeIndexed res;
    int n = res.mn = mn;
    std::vector<int> buf(n + 1, 0);
    for (auto [v, i] : E)
      ++buf[v];
    for (int i = 1; i <= n; i++)
      buf[i] += buf[i - 1];
    res.E.resize(buf[n]);
    for (int u = 0; u < n; u++)
      for (auto [v, i] : operator[](u))
        res.E[--buf[v]] = {u, i};
    res.I = std::move(buf);
    return res;
  }
};

} // namespace nachia

namespace nachia {

// simple undirected graph
std::vector<int> MaximumCardinalitySearch(const AdjacencyList &adj) {
  int n = adj.num_vertices();
  std::vector<int> res(n);
  std::vector<int> lp(n * 2 + 1), rp(n * 2 + 1);
  std::vector<int> idx(n, 0);
  for (int i = 0; i <= n * 2; i++)
    lp[i] = rp[i] = i;
  int li = n;
  auto Insert = [&](int i, int j) {
    rp[lp[j]] = i;
    lp[i] = lp[j];
    lp[j] = i;
    rp[i] = j;
  };
  auto Erase = [&](int i) {
    rp[lp[i]] = rp[i];
    lp[rp[i]] = lp[i];
  };
  for (int i = 0; i < n; i++)
    Insert(i, n);
  for (int i = 0; i < n; i++) {
    li++;
    while (lp[li] == li)
      li--;
    int v = lp[li];
    idx[v] = -1;
    Erase(v);
    for (int nx : adj[v])
      if (idx[nx] >= 0) {
        Erase(nx);
        Insert(nx, n + (++idx[nx]));
      }
    res[i] = v;
  }
  return res;
}

std::vector<int>
AdjacencyQuery(const AdjacencyList &adj,
               const std::vector<std::pair<int, int>> &queries) {
  int n = adj.num_vertices(), q = queries.size();
  std::vector<int> res(q, 0);
  AdjacencyListEdgeIndexed qadj(n, queries, false);
  std::vector<int> buf(n, -1);
  for (int i = 0; i < n; i++) {
    for (int nx : adj[i])
      buf[nx] = i;
    for (auto qi : qadj[i])
      if (buf[qi.to] == i)
        res[qi.edgeidx] = 1;
  }
  return res;
}

std::vector<int>
RecognizePerfectEliminationOrderling(const AdjacencyList &adj,
                                     const std::vector<int> &possiblePEO) {
  int n = adj.num_vertices();
  std::vector<int> invPEO(n);
  for (int i = 0; i < n; i++)
    invPEO[possiblePEO[i]] = i;
  std::vector<int> pre(n, -1);
  AdjacencyList adj2 = adj.permuted(invPEO);
  for (int i = 0; i < n; i++)
    for (int j : adj2[i])
      if (j < i && pre[i] < j)
        pre[i] = j;
  std::vector<std::pair<int, int>> queries;
  std::vector<int> Z;
  for (int i = 0; i < n; i++)
    if (pre[i] != -1) {
      for (int j : adj2[i])
        if (j < pre[i]) {
          queries.push_back(std::make_pair(pre[i], j));
          Z.push_back(i);
        }
    }
  auto qres = AdjacencyQuery(adj2, queries);
  int x = -1, y = -1, z = -1;
  for (int i = 0; i < (int)queries.size(); i++) {
    if (!qres[i]) {
      x = queries[i].second;
      y = queries[i].first;
      z = Z[i];
      break;
    }
  }
  if (z == -1)
    return {}; // it is PEO
  std::vector<int> dist(n, 0);
  std::vector<int> parent(n, -1);
  std::vector<int> bfs = {x, y};
  for (int inc : adj2[z])
    parent[inc] = -2;
  dist[x] = -1;
  dist[y] = 1;
  parent[x] = parent[y] = z;
  int d = n + 1, xx = -1, yy = -1;
  for (int i = 0; i < (int)bfs.size(); i++) {
    int p = bfs[i];
    for (int q : adj2[p])
      if (q < p && parent[q] != -2) {
        if (dist[p] < 0 && dist[q] > 0 && dist[q] - dist[p] < d) {
          d = dist[q] - dist[p];
          xx = p;
          yy = q;
        } else if (dist[p] > 0 && dist[q] < 0 && dist[p] - dist[q] < d) {
          d = dist[p] - dist[q];
          xx = q;
          yy = p;
        } else if (dist[q] == 0) {
          dist[q] = dist[p] + ((dist[p] < 0) ? -1 : 1);
          parent[q] = p;
          bfs.push_back(q);
        }
      }
  }
  std::vector<int> res(d + 1);
  int off = -dist[xx];
  res[off] = possiblePEO[z];
  do {
    res[dist[xx] + off] = possiblePEO[xx];
    xx = parent[xx];
  } while (xx != z);
  do {
    res[dist[yy] + off] = possiblePEO[yy];
    yy = parent[yy];
  } while (yy != z);
  return res;
}
} // namespace nachia

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> real_g(n);
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
      int u, v;
      cin >> u >> v;
      --u, --v;
      real_g[u].push_back(v);
      real_g[v].push_back(u);
      edges[i] = {u, v};
    }

    nachia::AdjacencyList adj(n, edges, true);
    auto mcs = nachia::MaximumCardinalitySearch(adj);
    std::reverse(mcs.begin(), mcs.end());
    vector<int> pos(n);
    for (int i = 0; i < n; ++i) {
      pos[mcs[i]] = i;
    }
    vector<int> part(n);
    bool fnd = false;
    for (int i = n - 1; i >= 0; --i) {
      ll sum_deg = real_g[i].size();
      ll cnt = 1;
      for (int j : real_g[i]) {
        if (pos[j] > pos[i]) {
          sum_deg += real_g[j].size();
          ++cnt;
        }
      }
      if (sum_deg - cnt * (cnt - 1) / 2 == m) {
        fnd = true;
        part.assign(n, 1);
        part[i] = 0;
        for (int j : real_g[i]) {
          if (pos[j] > pos[i]) {
            part[j] = 0;
          }
        }
        break;
      }
    }
    assert(fnd);

    auto update = [&](pair<int, int> &ans, int nans) {
      if (nans > ans.first) {
        ans = {nans, 0};
      }
      if (nans == ans.first) {
        ++ans.second;
      }
    };
    int clq_size = 0;
    for (int i = 0; i < n; ++i) {
      if (part[i] == 0) {
        ++clq_size;
      }
    }
    pair<int, int> clq_ans = {clq_size, 1};
    for (int i = 0; i < n; ++i) {
      if (part[i] == 1) {
        int cnt_ed = 0;
        for (int j : real_g[i]) {
          if (part[j] == 0) {
            ++cnt_ed;
          }
        }
        if (cnt_ed == clq_size) {
          update(clq_ans, clq_size + 1);
        } else if (cnt_ed + 1 == clq_size) {
          update(clq_ans, clq_size);
        }
      }
    }
    int aclq_size = 0;
    for (int i = 0; i < n; ++i) {
      if (part[i] == 1) {
        ++aclq_size;
      }
    }
    pair<int, int> aclq_ans = {aclq_size, 1};
    for (int i = 0; i < n; ++i) {
      if (part[i] == 0) {
        int cnt_ed = 0;
        for (int j : real_g[i]) {
          if (part[j] == 1) {
            ++cnt_ed;
          }
        }
        if (cnt_ed == 0) {
          update(aclq_ans, aclq_size + 1);
        } else if (cnt_ed == 1) {
          update(aclq_ans, aclq_size);
        }
      }
    }
    cout << clq_ans.second << ' ' << aclq_ans.second << '\n';
  }
}
Source code, Language: C++23

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

3
3 2
1 2
2 3
6 6
1 2
2 3
1 3
1 4
2 5
3 6
4 1
1 2

output:

2 1
1 4
1 2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 168ms
memory: 11440kb

input:

2231
1 0
5 7
4 1
3 4
3 1
3 5
4 2
3 2
4 5
5 4
2 1
2 5
2 4
2 3
5 10
3 2
2 5
1 4
4 2
4 5
1 2
1 3
3 5
3 4
1 5
5 10
1 3
2 4
1 4
5 2
2 3
1 5
5 4
1 2
3 4
5 3
5 9
2 5
3 5
2 3
2 1
4 3
3 1
4 1
4 5
2 4
5 4
4 2
4 1
4 5
4 3
5 9
4 1
4 5
3 4
2 4
2 1
3 1
2 5
3 5
3 2
5 4
2 5
2 3
2 1
2 4
5 9
5 2
1 3
4 3
1 2
5 4
4 2
5...

output:

1 1
3 1
4 1
1 5
1 5
2 1
4 1
2 1
4 1
2 1
2 1
3 1
4 1
4 1
1 5
2 1
4 1
1 5
1 5
1 5
3 1
4 1
4 1
4 1
3 1
3 1
4 1
4 1
2 1
4 1
4 1
1 5
1 5
2 1
4 1
4 1
4 1
3 1
2 1
4 1
2 1
4 1
4 1
4 1
3 1
1 5
4 1
4 1
1 5
2 1
4 1
2 1
2 1
1 5
4 1
1 5
3 1
4 1
1 5
2 1
1 5
3 1
3 1
1 5
3 1
3 1
2 1
1 5
4 1
3 1
1 5
2 1
3 1
2 1
2 1
...

result:

ok 2231 lines

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-05 07:46:33 | OpenSource Project