QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#330506 | #8055. Balance | ucup-team1198# | WA | 110ms | 13032kb | C++17 | 5.2kb | 2024-02-17 16:33:19 | 2024-02-17 16:33:19 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int MAXN = 200200;
vector<pair<int, int>> G1[MAXN];
int used[MAXN];
int tin[MAXN];
int tup[MAXN];
bool is_bridge[MAXN];
int ttime = 0;
void dfs1(int v, int p) {
++ttime;
used[v] = 1;
tin[v] = ttime;
tup[v] = ttime;
for (auto [u, i] : G1[v]) {
if (i == p)
continue;
if (used[u] == 0) {
dfs1(u, i);
if (tup[u] > tin[v]) {
is_bridge[i] = true;
}
tup[v] = min(tup[v], tup[u]);
} else if (used[u] == 1) {
tup[v] = min(tup[v], tin[u]);
}
}
used[v] = 2;
}
int id[MAXN];
int w[MAXN];
void dfs2(int v, int c) {
id[v] = c;
++w[c];
for (auto [u, i] : G1[v]) {
if (is_bridge[i])
continue;
if (id[u] == -1)
dfs2(u, c);
}
}
vector<int> G2[MAXN];
int sz[MAXN];
int up[MAXN];
void dfs3(int v, int p) {
up[v] = p;
sz[v] = w[v];
for (int u : G2[v]) {
if (u == p)
continue;
dfs3(u, v);
sz[v] += sz[u];
}
}
int n;
int get_or_tree_sz(int v, int u) {
if (up[u] == v) {
return sz[u];
}
return n - sz[v];
}
int total = 0;
void dfs4(int v, int p, int ban, int c, vector<int>& ans) {
ans[v] = c;
total += w[v];
for (int u : G2[v]) {
if (u == p || u == ban)
continue;
dfs4(u, v, ban, c, ans);
}
}
void solve() {
int m;
cin >> n >> m;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
--a;
--b;
G1[a].emplace_back(b, i);
G1[b].emplace_back(a, i);
edges[i] = make_pair(a, b);
}
map<int, int> cnt;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
vector<pair<int, int>> cnts;
for (auto kek : cnt)
cnts.emplace_back(kek.second, kek.first);
vector<int> pref_sums(cnts.size() + 1);
for (int i = 0; i < cnts.size(); ++i)
pref_sums[i + 1] = pref_sums[i] + cnts[i].first;
fill(is_bridge, is_bridge + m, false);
fill(used, used + n, 0);
fill(w, w + n, false);
dfs1(0, -1);
fill(id, id + n, -1);
int N = 0;
for (int i = 0; i < n; ++i) {
if (id[i] == -1) {
dfs2(i, N);
++N;
}
}
//cerr << N << '\n';
for (int i = 0; i < m; ++i) {
if (is_bridge[i]) {
auto [a, b] = edges[i];
a = id[a];
b = id[b];
G2[a].emplace_back(b);
G2[b].emplace_back(a);
//cerr << "bridge " << a << ' ' << b << '\n';
}
}
dfs3(0, -1);
if (N == 1) {
if (cnt.size() == 1) {
cout << "Yes\n";
for (int i = 0; i < n; ++i)
cout << cnts[0].second << ' ';
cout << '\n';
} else {
cout << "No\n";
}
} else {
vector<pair<int, int>> Q;
vector<int> par;
int q_st = 0;
vector<bool> is_leaf(N);
for (int i = 0; i < N; ++i) {
if (G2[i].size() == 1) {
int v = G2[i][0];
if (w[i] <= pref_sums[1]) {
Q.emplace_back(i, v);
par.emplace_back(-1);
G2[i].clear();
}
is_leaf[i] = true;
}
sort(G2[i].begin(), G2[i].end(), [&i](int a, int b) {
return get_or_tree_sz(i, a) < get_or_tree_sz(i, b);
});
}
bool ans = false;
while (q_st < Q.size()) {
auto [u, v] = Q[q_st];
++q_st;
if (is_leaf[v])
ans = true;
int was_cnt = get_or_tree_sz(v, u);
int i1 = upper_bound(pref_sums.begin(), pref_sums.end(), was_cnt) - pref_sums.begin();
bool extract_u = false;
while (!G2[v].empty()) {
if (G2[v].back() == u) {
G2[v].pop_back();
extract_u = true;
continue;
}
int nxt = G2[v].back();
int new_cnt = get_or_tree_sz(nxt, v);
if (pref_sums[i1] >= new_cnt) {
Q.emplace_back(v, nxt);
par.emplace_back(q_st - 1);
G2[v].pop_back();
} else {
break;
}
}
if (extract_u)
G2[v].emplace_back(u);
}
if (!ans) {
cout << "No\n";
} else {
cout << "Yes\n";
int cur = q_st - 1;
vector<int> path;
path.emplace_back(Q[cur].second);
while (cur != -1) {
path.emplace_back(Q[cur].first);
cur = par[cur];
}
reverse(path.begin(), path.end());
for (int i = 0; i < N; ++i) {
G2[i].clear();
}
for (int i = 0; i < m; ++i) {
if (is_bridge[i]) {
auto [a, b] = edges[i];
a = id[a];
b = id[b];
G2[a].emplace_back(b);
G2[b].emplace_back(a);
}
}
/*cerr << "path: ";
for (int v : path)
cerr << v << ' ';
cerr << '\n';*/
total = 0;
int cur_col = 0;
vector<int> ans(N);
for (int i = 0; i < path.size(); ++i) {
dfs4(path[i], (i + 1 == path.size() ? -1 : path[i + 1]), (i ? path[i - 1] : -1), cnts[cur_col].second, ans);
//cerr << total << ' ' << cur_col << '\n';
if (total == pref_sums[cur_col + 1])
++cur_col;
}
for (int i = 0; i < n; ++i)
cout << ans[id[i]] << ' ';
cout << '\n';
}
}
for (int i = 0; i < n; ++i)
G1[i].clear();
for (int i = 0; i < N; ++i)
G2[i].clear();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13008kb
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 3 1 2 2 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Wrong Answer
time: 110ms
memory: 13032kb
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 3 1 Yes 1 1 1 1 1 Yes 1 1 1 No No Yes 2 1 1 1 No No Yes 1 1 Yes 1 1 Yes 1 1 Yes 1 1 1 1 No Yes 1 1 1 1 1 Yes 1 1 1 1 1 Yes 1 1 1 Yes 2 1 Yes 1 1 1 1 1 Yes 2 1 No Yes 1 1 Yes 1 1 1 Yes 1 1 Yes 1 1 1 1 Yes 1 1 Yes 2 2 2 2 2 Yes 1 1 1 1 1 Yes 1 1 Yes 1 2 1 1 No Yes 1 1 N...
result:
wrong answer 4-th smallest numbers are not same (test case 2)