QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#447582 | #8757. 图 | ucup-team004# | RE | 55ms | 3780kb | C++20 | 2.4kb | 2024-06-18 16:47:37 | 2024-06-18 16:47:39 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::list<int>> e(2 * m);
std::vector<int> ep(2 * m);
std::vector<std::set<int>> adj(n);
std::vector<int> deg(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
ep[2 * i] = v;
ep[2 * i + 1] = u;
adj[u].insert(2 * i);
adj[v].insert(2 * i + 1);
deg[u]++;
deg[v]++;
}
const int k = (m - 1) / (n - 1) + 1;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> h;
for (int x = 0; x < n; x++) {
h.emplace(deg[x], x);
}
while (!h.empty()) {
auto [d, x] = h.top();
h.pop();
if (d != deg[x]) {
continue;
}
std::vector p(adj[x].begin(), adj[x].end());
adj[x].clear();
std::sort(p.begin(), p.end(),
[&](int i, int j) {
return ep[i] < ep[j];
});
for (int i = k - 1; i < p.size(); i++) {
if (ep[p[i]] == ep[p[i - k + 1]]) {
std::cout << x + 1 << " " << ep[p[i]] + 1 << "\n";
for (int j = i - k + 1; j <= i; j++) {
int u = p[j];
std::cout << 2 + e[u].size() << " " << x + 1 << " ";
for (auto y : e[u]) {
std::cout << y + 1 << " ";
}
std::cout << ep[u] + 1 << "\n";
}
return;
}
}
int t = std::max<int>(k - 1, (p.size() + 1) / 2);
for (int i = t; i < p.size(); i++) {
int u = p[i - t], v = p[i];
ep[u ^ 1] = ep[v];
ep[v ^ 1] = ep[u];
e[u ^ 1].push_back(x);
e[u ^ 1].splice(e[u ^ 1].end(), e[v]);
e[v ^ 1].push_back(x);
e[v ^ 1].splice(e[v ^ 1].end(), e[u]);
}
for (int i = p.size() - t; i < t; i++) {
adj[ep[p[i]]].erase(p[i] ^ 1);
h.emplace(--deg[ep[p[i]]], ep[p[i]]);
}
}
assert(false);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 55ms
memory: 3780kb
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 ...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: -100
Runtime Error
input:
10000 5 20 2 1 2 5 5 3 3 1 4 5 1 4 4 3 4 5 3 5 5 4 2 3 5 2 3 4 3 5 1 4 4 3 4 2 2 1 1 3 5 1 5 20 4 2 1 3 1 2 4 5 2 4 3 1 5 3 5 1 4 5 4 3 2 4 1 4 4 3 5 2 1 2 3 5 1 5 4 1 3 4 4 3 5 20 1 4 1 3 1 5 5 1 4 5 3 4 4 5 2 3 1 2 2 4 4 5 4 5 2 4 2 5 4 2 4 3 4 2 2 5 2 1 3 1 5 20 2 5 2 3 4 5 4 2 3 4 2 1 5 4 2 5 2 ...