QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #708491 | #6127. Kawa Exam | TheZone | AC ✓ | 332ms | 36848kb | C++20 | 5.1kb | 2024-11-03 22:53:52 | 2024-11-03 22:53:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N = 1e5 + 5;
int n, m, sz, ti, mx;
int a[N], cnt[N], num[N], siz[N], sum[N], rev[N], son[N];
int dfn[N], low[N], sd[N], ans[N];
vector<int> st, C[N];
vector<pair<int, int>> G[N], E[N];
void tarjan(int u, int from = 0) {
st.push_back(u);
dfn[u] = low[u] = ++ti;
for (auto [v, id] : G[u]) if (id != from) {
if (!dfn[v]) {
tarjan(v, id);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++sz;
while (1) {
int v = st.back();
st.pop_back();
sd[v] = sz;
C[sz].push_back(a[v]);
if (v == u) break;
}
}
}
void add(int u, int v) {
if (v == 1) mx = max(mx, cnt[u] + v);
else if (mx == cnt[u] && num[mx] == 1) mx--;
if (cnt[u]) num[cnt[u]]--;
if (cnt[u] += v) num[cnt[u]]++;
}
void dfs1(int u, int fa) {
dfn[u] = ++ti, rev[ti] = u, siz[u] = 1;
sum[u] = C[u].size();
for (auto [v, id] : E[u]) if (v != fa) {
dfs1(v, u);
siz[u] += siz[v];
sum[u] += sum[v];
if (sum[v] > sum[son[u]]) son[u] = v;
}
}
void dfs2(int u, int pa, int kp, int d, int dd = -1) {
for (auto [v, id] : E[u]) if (v != son[u] && id != pa) dfs2(v, id, 0, d, dd);
for (auto [v, id] : E[u]) if (v == son[u] && id != pa) dfs2(v, id, 1, d, dd);
for (auto x : C[u]) add(x, d);
for (auto [v, id] : E[u]) if (v != son[u] && id != pa) {
for (int i = dfn[v]; i < dfn[v] + siz[v]; ++i) {
int cur = rev[i];
for (auto x : C[cur]) add(x, d);
}
}
if (pa) ans[pa] += mx - (~dd ? dd : 0);
if (!kp) {
for (int i = dfn[u]; i < dfn[u] + siz[u]; ++i) {
int cur = rev[i];
for (auto x : C[cur]) add(x, -d);
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i], dfn[i] = low[i] = sd[i] = 0;
for (int i = 1, u, v; i <= m; ++i) {
ans[i] = 0;
cin >> u >> v;
G[u].push_back({v, i});
G[v].push_back({u, i});
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; ++u)
for (auto [v, id] : G[u]) if (sd[u] != sd[v]) {
E[sd[u]].push_back({sd[v], id});
}
ti = 0;
for (int i = 1; i <= sz; ++i) dfn[i] = 0;
int res = 0;
for (int i = 1; i <= sz; ++i) if (!dfn[i]) {
dfs1(i, 0);
dfs2(i, 0, 1, 1);
res += mx;
dfs2(i, 0, 1, -1, mx);
}
for (int i = 1; i <= m; ++i)
cout << ans[i] + res << " \n"[i == m];
for (int i = 1; i <= n; ++i) {
dfn[i] = low[i] = sd[i] = 0;
G[i].clear(), E[i].clear(), C[i].clear();
son[i] = 0;
}
for (int i = 1; i <= m; ++i) ans[i] = 0;
ti = sz = 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N = 1e5 + 5;
int n, m, sz, ti, mx;
int a[N], cnt[N], num[N], siz[N], sum[N], rev[N], son[N];
int dfn[N], low[N], sd[N], ans[N];
vector<int> st, C[N];
vector<pair<int, int>> G[N], E[N];
void tarjan(int u, int from = 0) {
st.push_back(u);
dfn[u] = low[u] = ++ti;
for (auto [v, id] : G[u]) if (id != from) {
if (!dfn[v]) {
tarjan(v, id);
low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++sz;
while (1) {
int v = st.back();
st.pop_back();
sd[v] = sz;
C[sz].push_back(a[v]);
if (v == u) break;
}
}
}
void add(int u, int v) {
if (v == 1) mx = max(mx, cnt[u] + v);
else if (mx == cnt[u] && num[mx] == 1) mx--;
if (cnt[u]) num[cnt[u]]--;
if (cnt[u] += v) num[cnt[u]]++;
}
void dfs1(int u, int fa) {
dfn[u] = ++ti, rev[ti] = u, siz[u] = 1;
sum[u] = C[u].size();
for (auto [v, id] : E[u]) if (v != fa) {
dfs1(v, u);
siz[u] += siz[v];
sum[u] += sum[v];
if (sum[v] > sum[son[u]]) son[u] = v;
}
}
void dfs2(int u, int pa, int kp, int d, int dd = -1) {
for (auto [v, id] : E[u]) if (v != son[u] && id != pa) dfs2(v, id, 0, d, dd);
for (auto [v, id] : E[u]) if (v == son[u] && id != pa) dfs2(v, id, 1, d, dd);
for (auto x : C[u]) add(x, d);
for (auto [v, id] : E[u]) if (v != son[u] && id != pa) {
for (int i = dfn[v]; i < dfn[v] + siz[v]; ++i) {
int cur = rev[i];
for (auto x : C[cur]) add(x, d);
}
}
if (pa) ans[pa] += mx - (~dd ? dd : 0);
if (!kp) {
for (int i = dfn[u]; i < dfn[u] + siz[u]; ++i) {
int cur = rev[i];
for (auto x : C[cur]) add(x, -d);
}
}
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i], dfn[i] = low[i] = sd[i] = 0;
for (int i = 1, u, v; i <= m; ++i) {
ans[i] = 0;
cin >> u >> v;
G[u].push_back({v, i});
G[v].push_back({u, i});
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
for (int u = 1; u <= n; ++u)
for (auto [v, id] : G[u]) if (sd[u] != sd[v]) {
E[sd[u]].push_back({sd[v], id});
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7796kb
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: 332ms
memory: 34676kb
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: 221ms
memory: 34108kb
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: 240ms
memory: 36848kb
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: 259ms
memory: 28732kb
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: 274ms
memory: 26680kb
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: 258ms
memory: 26032kb
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: 274ms
memory: 25484kb
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