QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#447580#8757. 图ucup-team004#RE 53ms3632kbC++202.3kb2024-06-18 16:46:322024-06-18 16:46:33

Judging History

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

  • [2024-06-18 16:46:33]
  • 评测
  • 测评结果:RE
  • 用时:53ms
  • 内存:3632kb
  • [2024-06-18 16:46:32]
  • 提交

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);
        }
    }
    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: 53ms
memory: 3632kb

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 ...

output:

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

result: