QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #563983 | #6413. Classical Graph Theory Problem | A_programmer | WA | 7ms | 23148kb | C++17 | 5.9kb | 2024-09-14 18:21:55 | 2024-09-14 18:21:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
bool vis[maxn];
set<int> g[maxn];
int nxt[maxn], n, m;
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> h[maxn], vec, ansS, ansT, reS, reT, reC, dot;
vector<pii> p[maxn];
int bel[maxn], T, TT;
void dfs(int u)
{
vis[u] = 1; dot.emplace_back(u);
for (auto [v, w] : p[u]) if (!vis[v]) dfs(v);
}
void work()
{
cin >> n >> m; vec.clear(); ansS.clear(), ansT.clear();
for (int i = 1; i <= n; i++) g[i].clear(), h[i].clear(), p[i].clear(), vis[i] = nxt[i] = bel[i] = 0;
for (int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
g[u].insert(v); g[v].insert(u);
h[u].emplace_back(v), h[v].emplace_back(u);
}
while (pq.size()) pq.pop();
for (int i = 1; i <= n; i++) pq.push(make_pair(g[i].size(), i));
while (pq.size())
{
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1; bool Fl = false;
for (int v : g[u])
if (!vis[v])
{
vis[v] = 1;
Fl = true;
nxt[u] = v, nxt[v] = u;
for (int x : g[u]) if (x != v) g[x].erase(u);
for (int x : g[v]) if (x != u) g[x].erase(v);
break;
}
if (!Fl) vec.emplace_back(u);
}
for (int i = 1; i <= n; i++) if (!vis[i]) pq.push(make_pair(g[i].size(), i));
while (pq.size())
{
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1; bool Fl = false;
for (int v : g[u])
if (!vis[v])
{
vis[v] = 1;
Fl = true;
nxt[u] = v, nxt[v] = u;
for (int x : g[u]) if (x != v) g[x].erase(u), pq.push(make_pair(g[x].size(), x));
for (int x : g[v]) if (x != u) g[x].erase(v), pq.push(make_pair(g[x].size(), x));
break;
}
if (!Fl) vec.emplace_back(u);
}
for (int u : vec)
{
int pos1 = 0, pos2 = 0;
for (int v : h[u])
if (nxt[v])
{
if (!pos1) pos1 = pos2 = v;
else pos2 = v;
}
p[pos1].emplace_back(make_pair(pos2, u));
if (pos1 != pos2) p[pos2].emplace_back(make_pair(pos1, u));
}
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= n; i++)
{
if (!nxt[i] || vis[i]) continue;
if (!p[i].size())
{
if (!p[nxt[i]].size()) bel[i] = 1, bel[nxt[i]] = 2, vis[i] = vis[nxt[i]] = 1;
continue;
}
reS.clear(), reT.clear(), reC.clear(), dot.clear(), dfs(i);
sort(dot.begin(), dot.end());
// for (int u : dot) cout << u << " "; cout << endl;
for (int u : dot)
{
int cnt1 = 0, cnt2 = 0;
for (auto [v, w] : p[u])
{
if (v > u) continue;
if (bel[v] == 1) cnt1++;
else if (bel[v] == 2) cnt2++;
}
if (cnt1 < cnt2)
{
bel[u] = 1;
for (auto [v, w] : p[u])
{
if (v > u) continue;
if (bel[v] == 1) reS.emplace_back(w);
else reC.emplace_back(w);
}
}
else if (cnt1 > cnt2)
{
bel[u] = 2;
for (auto [v, w] : p[u])
{
if (v > u) continue;
if (bel[v] == 2) reT.emplace_back(w);
else reC.emplace_back(w);
}
}
else
{
if (reS.size() < reT.size())
{
bel[u] = 1;
for (auto [v, w] : p[u])
{
if (v > u) continue;
if (bel[v] == 1) reS.emplace_back(w);
else reC.emplace_back(w);
}
}
else
{
bel[u] = 2;
for (auto [v, w] : p[u])
{
if (v > u) continue;
if (bel[v] == 2) reT.emplace_back(w);
else reC.emplace_back(w);
}
}
}
}
while (reC.size())
{
if (reS.size() < reT.size()) reS.emplace_back(reC.back()), reC.pop_back();
else reT.emplace_back(reC.back()), reC.pop_back();
}
if (reS.size() < reT.size())
{
swap(reS, reT);
for (int u : dot) bel[u] = 3 - bel[u];
}
if (ansS.size() < ansT.size())
{
for (int x : reS) ansS.emplace_back(x);
for (int x : reT) ansT.emplace_back(x);
}
else
{
for (int u : dot) bel[u] = 3 - bel[u];
for (int x : reS) ansT.emplace_back(x);
for (int x : reT) ansS.emplace_back(x);
}
}
for (int i = 1; i <= n; i++)
if (nxt[i])
{
if (!bel[i]) bel[i] = 3 - bel[nxt[i]];
if (bel[i] == 1) ansT.emplace_back(i);
else ansS.emplace_back(i);
}
if (TT == 46) return;
if (ansS.size() == n / 2) for (int x : ansS) cout << x << " ";
else for (int x : ansT) cout << x << " "; cout << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
for (TT = 1; TT <= T; TT++)
{
work();
if (TT == 46)
{
cout << n << " " << m << endl;
for (int i = 1; i <= n; i++, cout << endl)
for (int v : h[i]) cout << v << " ";
return 0;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 23124kb
input:
2 6 7 1 2 1 3 2 3 3 4 4 5 4 6 5 6 3 2 1 2 2 3
output:
6 2 4 2
result:
ok ok (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 23148kb
input:
10000 2 1 1 2 29 28 13 19 16 5 21 7 22 10 10 2 1 18 27 13 10 3 11 23 12 22 11 7 7 17 29 17 9 1 28 21 2 18 13 9 4 25 20 16 5 14 20 7 14 4 12 8 8 24 17 19 15 1 11 6 26 9 13 12 13 9 12 2 6 12 9 11 5 2 8 10 6 10 3 10 7 1 7 5 8 9 4 1 12 11 10 6 2 8 12 4 5 10 11 1 3 1 10 1 12 9 9 1 8 3 7 1 35 35 13 8 34 1...
output:
2 19 10 11 14 15 17 18 20 22 24 25 26 27 28 8 1 2 3 9 12 9 6 1 2 4 5 5 26 3 9 13 15 18 23 24 28 29 30 31 32 33 34 35 8 18 4 7 10 11 15 16 17 2 3 4 26 32 45 4 7 10 11 13 15 22 24 27 28 31 35 37 40 42 43 44 46 47 48 49 50 21 27 35 30 1 7 8 12 13 15 18 19 23 26 29 31 33 36 12 14 3 4 5 6 9 6 ...
result:
wrong answer vertex 18 is repeated twice in the output (test case 46)