QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#129843 | #6127. Kawa Exam | Energy_is_not_over | AC ✓ | 808ms | 44664kb | C++17 | 7.7kb | 2023-07-23 01:58:32 | 2023-07-23 01:58:36 |
Judging History
answer
//
// Created by BigBag on 22.07.2023 12:32:01
//
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
template<typename T>
ostream& operator << (ostream &os, const vector<T> &v) {
bool f = 1;
os << "[";
for (const auto &x : v) {
if (!f) {
os << " ";
}
f = 0;
os << x;
}
os << "]";
return os;
}
const int max_n = 100111, inf = 1000111222;
struct segment_tree {
int val[max_n], distr[max_n], ans;
segment_tree() {
distr[0] = inf;
}
void inc(int x) {
--distr[val[x]];
++val[x];
++distr[val[x]];
ans = max(ans, val[x]);
}
void dec(int x) {
--distr[val[x]];
if (distr[val[x]] == 0 && val[x] == ans) {
--ans;
}
--val[x];
++distr[val[x]];
}
void op(int x, int val, bool store = true) {
if (store) {
ops.push_back({x, val});
}
if (val == 1) {
inc(x);
} else {
assert(val == -1);
dec(x);
}
}
void restore() {
while (!ops.empty()) {
op(ops.back().first, -ops.back().second, false);
ops.pop_back();
}
}
vector<pair<int, int>> ops;
};
segment_tree st;
int DIFF;
int t, n, m, a[max_n];
int sz[max_n], vis[max_n], delta[max_n], val1[max_n], val2[max_n];
vector<int> g3[max_n];
vector<int> all[max_n];
map<pair<int, int>, int> ids;
void dfs3(int v, int p) {
vis[v] = 1;
for (int i = 0; i < g3[v].size(); ++i) {
if (g3[v][i] == p) {
swap(g3[v][i], g3[v].back());
g3[v].pop_back();
break;
}
}
sz[v] = all[v].size();
for (int to : g3[v]) {
dfs3(to, v);
sz[v] += sz[to];
}
for (int i = 0; i < g3[v].size(); ++i) {
if (sz[g3[v].back()] < sz[g3[v][i]]) {
swap(g3[v].back(), g3[v][i]);
}
}
}
int L[max_n], R[max_n];
vector<int> order;
void dfs33(int v) {
L[v] = order.size();
order.push_back(v);
R[v] = order.size();
for (int to : g3[v]) {
dfs33(to);
if (to != g3[v].back()) {
R[v] = order.size();
}
}
}
void add(int v, int val) {
for (int x : all[v]) {
st.op(a[x], val);
}
}
void add_rec(int v, int val, bool is_root = true) {
if (0) {
for (int i = L[v]; i < R[v]; ++i) {
add(order[i], val);
}
} else {
add(v, val);
for (int to : g3[v]) {
if (is_root && to == g3[v].back()) {
break;
}
add_rec(to, val, false);
}
}
}
void dfs4(int v) {
// LOG(v, all[v]);
st.restore();
for (int to : g3[v]) {
st.restore();
dfs4(to);
}
add_rec(v, 1);
val1[v] = st.ans;
}
void dfs5(int v) {
// LOG(v, all[v]);
st.restore();
// st = st2;
for (int to : g3[v]) {
st.restore();
// st = st2;
dfs5(to);
}
add_rec(v, -1);
val2[v] = st.ans;
}
int ADD;
void dfs6(int v) {
// LOG(v, all[v]);
for (int to : g3[v]) {
dfs6(to);
LOG(v, to, all[to], ADD, val1[to], val2[to]);
delta[ids[{min(v, to), max(v, to)}]] = ADD + val1[to] + val2[to];
}
}
int used[max_n], cur_t, tin[max_n], fup[max_n], is_bridge[max_n];
int U[max_n], V[max_n];
vector<int> g[max_n], g2[max_n];
void compress_a() {
vector<int> v(a, a + n);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
DIFF = v.size() - 1;
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
}
}
void clr() {
ids.clear();
order.clear();
for (int i = 0; i <= n; ++i) {
g[i].clear();
g2[i].clear();
g3[i].clear();
used[i] = tin[i] = fup[i] = 0;
all[i].clear();
}
for (int i = 0; i <= m; ++i) {
is_bridge[i] = 0;
}
}
void dfs(int v, int pid) {
tin[v] = fup[v] = ++cur_t;
used[v] = 1;
for (int to_id : g[v]) {
if (to_id == pid) {
continue;
}
const int to = v ^ U[to_id] ^ V[to_id];
if (!used[to]) {
dfs(to, to_id);
if (fup[to] > tin[v]) {
is_bridge[to_id] = 1;
}
fup[v] = min(fup[v], fup[to]);
} else {
fup[v] = min(fup[v], tin[to]);
}
}
}
void dfs2(int v) {
used[v] = cur_t;
all[cur_t].push_back(v);
for (int to : g2[v]) {
if (!used[to]) {
dfs2(to);
}
}
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < m; ++i) {
cin >> U[i] >> V[i];
--U[i];
--V[i];
}
compress_a();
for (int i = 0; i < m; ++i) {
g[U[i]].push_back(i);
g[V[i]].push_back(i);
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i, -1);
}
}
for (int i = 0; i < m; ++i) {
if (!is_bridge[i]) {
g2[U[i]].push_back(V[i]);
g2[V[i]].push_back(U[i]);
}
}
fill(used, used + n, 0);
cur_t = 0;
for (int i = 0; i < n; ++i) {
if (!used[i]) {
++cur_t;
dfs2(i);
LOG(cur_t, all[cur_t]);
}
}
for (int i = 0; i < m; ++i) {
if (is_bridge[i]) {
g3[used[U[i]]].push_back(used[V[i]]);
g3[used[V[i]]].push_back(used[U[i]]);
ids[{min(used[U[i]], used[V[i]]),
max(used[U[i]], used[V[i]])}] = i;
}
}
st.restore();
int total = 0;
fill(vis + 1, vis + cur_t + 1, 0);
for (int i = 1; i <= cur_t; ++i) {
if (vis[i]) {
continue;
}
dfs3(i, -1);
order.clear();
dfs33(i);
dfs4(i);
int val = st.ans;
LOG(i, val);
total += val;
ADD = -val;
auto cops = st.ops;
st.ops.clear();
dfs5(i);
dfs6(i);
st.restore();
st.ops = cops;
st.restore();
}
LOG(total);
for (int i = 0; i < m; ++i) {
if (is_bridge[i]) {
cout << total + delta[i];
} else {
cout << total;
}
if (i + 1 < m) {
cout << " ";
}
}
cout << "\n";
clr();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 17448kb
input:
3 7 5 1 2 1 2 1 2 1 1 2 1 3 2 4 5 6 5 7 3 3 1 2 3 1 2 1 3 2 3 2 3 12345 54321 1 2 1 2 1 1
output:
6 5 5 5 4 1 1 1 1 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 808ms
memory: 44664kb
input:
5557 2 7 79960 79960 2 2 1 1 1 1 2 2 1 1 2 1 1 2 9 8 21881 70740 70740 21881 22458 22458 639 21881 70740 3 3 1 6 5 8 7 5 5 7 2 3 5 1 7 6 6 7 13064 20716 6746 13064 6746 69225 5 5 4 1 4 1 1 6 4 5 3 2 3 2 8 4 45146 14400 45146 45146 14400 72969 14400 45146 8 6 1 3 4 6 8 3 18 13 48132 37949 92338 92338...
output:
2 2 2 2 2 2 2 6 6 7 6 6 6 6 6 3 3 3 4 4 3 3 7 7 7 7 9 9 9 8 9 8 9 8 9 9 10 9 9 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9 10 9 16 16 16 16 16 17 16 16 10 10 11 10 12 11 10 10 10 10 10 10 10 12 10 10 10 10 10 11 10 9 9 9 9 9 9 9 9 9 9 9 9 9 10 ...
result:
ok 5557 lines
Test #3:
score: 0
Accepted
time: 469ms
memory: 42788kb
input:
10 100000 99999 3983 3983 20157 97983 20157 20157 3983 3983 97983 20157 20157 3983 97983 20157 3983 20157 20157 3983 3983 3983 97983 97983 20157 3983 3983 97983 20157 97983 20157 97983 3983 97983 97983 3983 20157 3983 20157 20157 97983 3983 3983 3983 3983 97983 97983 3983 97983 97983 3983 20157 3983...
output:
33392 33393 33393 33393 33393 33392 33392 33393 33393 33393 33392 33393 33393 33392 33393 33393 33392 33392 33392 33393 33393 33393 33392 33392 33393 33393 33393 33393 33393 33392 33393 33393 33392 33393 33392 33393 33393 33393 33392 33392 33392 33392 33393 33393 33392 33393 33393 33392 33393 33392 ...
result:
ok 10 lines
Test #4:
score: 0
Accepted
time: 513ms
memory: 42496kb
input:
10 100000 99999 27534 27534 3780 3780 27534 53544 27534 3780 3780 53544 53544 27534 53544 53544 3780 3780 3780 3780 53544 27534 3780 3780 53544 27534 27534 53544 27534 27534 53544 27534 27534 27534 3780 27534 27534 3780 3780 3780 27534 53544 3780 53544 27534 3780 3780 3780 27534 27534 27534 3780 275...
output:
33613 33601 33601 33600 33600 33601 33601 33601 33600 33601 33600 33600 33601 33601 33601 33601 33601 33601 33600 33600 33601 33601 33601 33601 33600 33601 33601 33600 33601 33600 33601 33600 33601 33601 33601 33601 33600 33601 33601 33601 33601 33601 33601 33601 33601 33601 33600 33601 33600 33601 ...
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 507ms
memory: 36404kb
input:
10 100000 99999 92499 92270 92270 92499 92499 92499 92270 54017 92270 92270 92270 54017 54017 54017 54017 92270 92499 54017 92270 54017 92499 92499 92270 92270 54017 54017 54017 54017 92270 92270 92499 54017 54017 92499 92499 54017 92270 92270 54017 92499 92270 92270 54017 54017 54017 92499 92499 54...
output:
33506 33482 33507 33482 33508 33483 33508 33483 33508 33483 33507 33483 33506 33483 33505 33483 33503 33483 33503 33482 33504 33483 33505 33483 33504 33483 33502 33483 33501 33483 33500 33482 33502 33483 33500 33483 33501 33482 33502 33483 33501 33483 33500 33482 33500 33483 33498 33483 33499 33483 ...
result:
ok 10 lines
Test #6:
score: 0
Accepted
time: 493ms
memory: 36400kb
input:
10 100000 99999 76207 76207 88551 88551 98176 76207 98176 88551 88551 98176 88551 76207 76207 98176 98176 76207 76207 88551 76207 88551 76207 88551 88551 76207 88551 76207 98176 88551 76207 98176 88551 88551 76207 88551 98176 88551 76207 76207 98176 88551 76207 98176 76207 88551 88551 88551 88551 76...
output:
33484 33484 33476 33484 33477 33485 33476 33485 33477 33485 33477 33486 33477 33484 33477 33485 33476 33485 33476 33485 33476 33483 33477 33483 33477 33485 33476 33485 33477 33485 33476 33487 33476 33487 33476 33486 33477 33486 33476 33486 33477 33486 33476 33486 33476 33486 33477 33487 33477 33487 ...
result:
ok 10 lines
Test #7:
score: 0
Accepted
time: 525ms
memory: 36324kb
input:
10 100000 99999 70486 49904 70486 49904 87935 49904 49904 87935 87935 49904 49904 87935 49904 87935 87935 70486 49904 87935 87935 49904 70486 87935 49904 70486 87935 87935 49904 49904 49904 87935 70486 70486 70486 49904 70486 87935 87935 87935 70486 87935 70486 49904 87935 49904 49904 87935 70486 87...
output:
33491 33486 33489 33486 33489 33486 33489 33486 33487 33486 33487 33486 33486 33485 33486 33486 33486 33486 33485 33486 33485 33485 33486 33486 33485 33486 33485 33486 33485 33485 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33485 33486 33485 ...
result:
ok 10 lines
Test #8:
score: 0
Accepted
time: 535ms
memory: 36300kb
input:
10 100000 99999 98004 33580 98004 98004 98004 92291 92291 98004 98004 92291 92291 33580 98004 92291 33580 98004 98004 33580 98004 92291 92291 33580 92291 92291 98004 33580 98004 33580 33580 98004 33580 92291 33580 33580 92291 92291 92291 98004 33580 98004 92291 92291 33580 92291 98004 98004 92291 92...
output:
33462 33463 33421 33463 33422 33465 33421 33463 33422 33464 33422 33462 33422 33464 33421 33464 33422 33464 33422 33465 33422 33463 33422 33462 33422 33463 33422 33465 33421 33464 33422 33464 33422 33463 33422 33463 33421 33463 33421 33462 33422 33460 33422 33461 33421 33461 33422 33460 33422 33459 ...
result:
ok 10 lines