QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#69121 | #5239. Mędrcy [A] | ivgechu | Compile Error | / | / | C++14 | 3.7kb | 2022-12-24 03:20:36 | 2022-12-24 03:20:37 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2022-12-24 03:20:37]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2022-12-24 03:20:36]
- 提交
answer
#include <bits/stdc++.h>
#define dbg(x) " [" << #x << ": " << (x) << "] "
using namespace std;
template<typename A, typename B>
ostream& operator<<(ostream& out, const pair<A,B>& p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& c) {
out << "{";
for(auto it = c.begin(); it != c.end(); it++) {
if(it != c.begin()) out << ", ";
out << *it;
}
return out << "}";
}
struct Test {
int n,m,k;
vector<int> u;
int mn;
vector<int> in_ans;
void rec(vector<vector<int>> g, int used, int edges) {
if(edges == 0) {
if(used == 0) return;
if(used < mn) {
mn = used;
in_ans.assign(n, 0);
}
if(used == mn) {
for(int i = 0; i < n; i++) {
if(u[i] == 2) {
in_ans[i] = 1;
}
}
}
return;
}
if(used >= k || used >= mn) return;
int j = -1;
for(int i = 0; i < n; i++) {
if(u[i]) continue;
if(j == -1 || g[i].size() > g[j].size()) j = i;
}
if(edges > g[j].size() * (k - used)) return;
vector<int> nxt = g[j];
for(int v : nxt) {
g[v].erase(find(g[v].begin(), g[v].end(), j));
}
g[j].clear();
u[j] = 2;
edges -= nxt.size();
rec(g, used + 1, edges);
u[j] = 1;
for(int v : nxt) {
vector<int> nxt2 = g[v];
for(int vv : nxt2) {
g[vv].erase(find(g[vv].begin(), g[vv].end(), v));
}
g[v].clear();
edges -= nxt2.size();
u[v] = 2;
}
rec(g, used + nxt.size(), edges);
for(int v : nxt) u[v] = 0;
u[j] = 0;
}
void solve() {
cin >> n >> m >> k;
set<pair<int,int>> st;
vector<vector<int>> g(n);
u.resize(n);
vector<pair<int,int>> e;
vector<int> d(n);
in_ans.resize(n);
for(int i = 0; i < m; i++) {
int a,b;
cin >> a >> b;
a--;
b--;
if(a > b) swap(a, b);
if(st.contains({a,b})) continue;
st.insert({a,b});
e.push_back({a,b});
d[a]++;
d[b]++;
}
int used = 0;
for(int i = 0; i < n; i++) {
if(d[i] > k) {
u[i] = 2;
in_ans[i] = 1;
used++;
}
}
int edges = 0;
for(auto [a,b] : e) {
if(!in_ans[a] && !in_ans[b]) {
g[a].push_back(b);
g[b].push_back(a);
edges++;
}
}
for(int i = 0; i < n; i++) {
if(g[i].size() == 0 && !in_ans[i]) u[i] = 1;
}
in_ans.assign(n, 0);
mn = k + 1;
rec(g, used, edges);
if(mn == k + 1) {
cout << -1 << '\n';
return;
}
cout << mn << " ";
int y = 0;
for(int i = 0; i < n; i++) y += in_ans[i];
cout << y << '\n';
y = 0;
for(int i = 0; i < n; i++) {
if(in_ans[i]) {
if(y) cout << " ";
cout << i + 1;
y++;
}
}
cout << '\n';
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test_num = 1;
cin >> test_num;
for(int i = 1; i <= test_num; i++) {
Test t;
t.solve();
}
return 0;
}
详细
answer.code: In member function ‘void Test::solve()’: answer.code:81:19: error: ‘class std::set<std::pair<int, int> >’ has no member named ‘contains’ 81 | if(st.contains({a,b})) continue; | ^~~~~~~~ answer.code:96:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ 96 | for(auto [a,b] : e) { | ^