QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#160412 | #7107. Chaleur | ucup-team1191# | AC ✓ | 168ms | 11440kb | C++23 | 11.2kb | 2023-09-02 20:23:53 | 2023-09-02 20:23:55 |
Judging History
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';
}
}
这程序好像有点Bug,我给组数据试试?
详细
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