QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #331097 | #8055. Balance | ucup-team296# | WA | 147ms | 3740kb | C++20 | 5.7kb | 2024-02-18 00:07:22 | 2024-02-18 00:07:23 |
Judging History
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct test {
vector<int> e;
vector<vector<int>> g;
vector<int> tin;
vector<int> up;
vector<int> st;
int cc = 0;
vector<int> comp;
int t = 0;
void dfs(int x, int ee) {
tin[x] = up[x] = t++;
st.push_back(x);
for (int i: g[x]) {
if (i == (ee ^ 1)) continue;
int y = e[i];
if (tin[y] == -1) {
dfs(y, i);
if (up[y] > x) {
while (st.back() != y) {
comp[st.back()] = cc;
st.pop_back();
}
comp[y] = cc;
st.pop_back();
cc++;
}
up[x] = min(up[x], up[y]);
} else {
up[x] = min(up[x], tin[y]);
}
}
}
vector<int> sz;
vector<vector<int>> gg;
int k;
vector<int> ps, ss;
vector<int> mxp, mxs;
void dfs_sz(int x, int p) {
for (int y: gg[x]) {
if (y == p) continue;
dfs_sz(y, x);
sz[x] += sz[y];
}
}
vector<int> res;
vector<int> vals;
bool ok = false;
void fill(int x, int v, int p) {
res[x] = v;
for (int y: gg[x]) {
if (y == p) continue;
fill(y, v, x);
}
}
void fill_p(int x, int v, int p) {
if (v == 0) return;
if (sz[x] == ps[v - 1]) {
v--;
}
res[x] = v;
bool done = false;
for (int y: gg[x]) {
if (y == p) continue;
if (mxp[y] == v && !done) {
fill_p(y, v, x);
done = true;
} else {
fill(y, v, x);
}
}
}
void fill_s(int x, int v, int p) {
if (v == 0) return;
if (sz[x] == ss[v - 1]) {
v--;
}
res[x] = k - 1 - v;
bool done = false;
for (int y: gg[x]) {
if (y == p) continue;
if (mxs[y] == v && !done) {
fill_s(y, v, x);
done = true;
} else {
fill(y, k - 1 - v, x);
}
}
}
void print_ans() {
cout << "Yes\n";
for (int i = 0; i < (int)comp.size(); i++) {
cout << vals[res[comp[i]]] << " ";
}
cout << "\n";
ok = true;
}
void dfs2(int x, int p) {
for (int y: gg[x]) {
if (y == p) continue;
dfs2(y, x);
if (ok) return;
mxp[x] = max(mxp[x], mxp[y]);
mxs[x] = max(mxs[x], mxs[y]);
}
if (sz[x] == ps[mxp[x]]) mxp[x]++;
if (sz[x] == ss[mxs[x]]) mxs[x]++;
for (int _ = 0; _ < 2; _++) {
int l = -1;
int z = 0;
for (int y: gg[x]) {
if (y == p) continue;
if (mxs[y] + z == k - 1) {
res.assign(res.size(), z);
fill_p(l, z, x);
fill_s(y, mxs[y], x);
print_ans();
return;
}
if (mxp[y] > z) {
z = mxp[y];
l = y;
}
}
reverse(gg[x].begin(), gg[x].end());
}
}
void solve() {
int n, m;
cin >> n >> m;
e.resize(2 * m);
g.resize(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
e[2 * i] = y;
g[x].push_back(2 * i);
e[2 * i + 1] = x;
g[y].push_back(2 * i + 1);
}
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
tin.assign(n, -1);
up.resize(n);
comp.resize(n);
dfs(0, -1);
while (!st.empty()) {
comp[st.back()] = cc;
st.pop_back();
}
cc++;
// for (int i = 0; i < n; i++) {
// cout << comp[i] << " ";
// }
sz.resize(cc);
gg.resize(cc);
for (int i = 0; i < n; i++) {
sz[comp[i]]++;
for (int _: g[i]) {
int j = e[_];
if (comp[j] != comp[i]) {
gg[comp[i]].push_back(comp[j]);
}
}
}
dfs_sz(0, -1);
sort(a.begin(), a.end());
vector<pair<int, int>> st;
for (int x: a) {
if (!st.empty() && x == st.back().first) {
st.back().second++;
} else {
st.push_back({x, 1});
}
}
k = st.size();
vector<int> c(k);
vals.resize(k);
for (int i = 0; i < k; i++) {
c[i] = st[i].second;
vals[i] = st[i].first;
}
ps.resize(k);
ps[0] = c[0];
for (int i = 1; i < k; i++) {
ps[i] = ps[i - 1] + c[i];
}
ss.resize(k);
ss[0] = c[k - 1];
for (int i = 1; i < k; i++) {
ss[i] = ss[i - 1] + c[k - 1 - i];
}
mxp.resize(cc);
mxs.resize(cc);
res.resize(cc);
dfs2(0, -1);
if (!ok) {
cout << "No\n";
}
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
test().solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
5 5 4 1 2 2 3 3 4 4 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 2 2 3 5 6 1 2 1 2 2 3 3 4 4 5 3 5 1 2 1 2 1 2 2 1 2 1 2 1 2
output:
Yes 5 4 3 2 1 No Yes 2 2 1 3 2 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 147ms
memory: 3740kb
input:
100000 4 3 4 2 1 3 2 1 2 1 3 2 5 7 2 5 5 3 2 3 5 1 4 3 2 4 4 3 1 3 1 1 2 3 2 2 1 2 3 1 1 1 4 7 3 4 1 4 2 3 4 3 4 2 3 1 4 3 2 3 3 2 4 6 2 4 3 1 1 2 1 2 2 3 4 2 1 1 3 3 4 7 3 2 4 2 1 2 3 4 3 2 2 4 3 4 2 1 1 1 5 5 3 2 1 5 4 5 4 3 2 1 1 2 2 3 2 3 5 2 3 1 3 3 1 3 1 2 1 3 2 3 2 3 2 1 2 1 1 2 1 1 2 3 2 1 1...
output:
Yes 2 2 1 3 No Yes 1 1 1 No No Yes 2 1 1 1 No No No No No No No Yes 1 1 1 1 1 No Yes 1 1 1 Yes 2 1 Yes 1 1 1 1 1 Yes 2 1 No No Yes 1 1 1 Yes 1 1 No No No No Yes 1 1 Yes 1 2 1 1 No No No Yes 1 1 No No No Yes 2 1 1 1 1 Yes 2 1 1 1 No No No No No No No Yes 1 1 Yes 2 2 1 No Yes 2 2 No ...
result:
wrong answer ans finds an answer, but out doesn't (test case 9)