QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139022 | #6127. Kawa Exam | thenymphsofdelphi | AC ✓ | 586ms | 34152kb | C++20 | 6.1kb | 2023-08-12 16:33:49 | 2023-08-12 16:33:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1e5 + 5;
struct disjoint_set_union{
int par[N];
void reset(int sz = N){
fill(par, par + sz, -1);
}
int root(int x){
return par[x] < 0 ? x : (par[x] = root(par[x]));
}
bool merge(int x, int y){
if ((x = root(x)) == (y = root(y))){
return false;
}
if (par[x] > par[y]){
swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
} dsu;
struct counter{
int cnt[N];
int cnt_cnt[N];
int ans;
void insert(int x){
cnt_cnt[cnt[x]]--;
cnt[x]++;
cnt_cnt[cnt[x]]++;
if (ans < cnt[x]){
ans = cnt[x];
}
}
void erase(int x){
cnt_cnt[cnt[x]]--;
cnt[x]--;
cnt_cnt[cnt[x]]++;
if (cnt_cnt[ans] == 0){
ans--;
}
}
} DS, DSout, DSin;
struct edge{
int u, v;
};
int n, m;
int color[N];
edge a[N];
vector <int> adj[N];
int ctrtime, time_in[N], low[N];
bool bridge[N];
void dfs_time(int u, int ip = -1){
time_in[u] = ++ctrtime;
low[u] = time_in[u];
for (auto i: adj[u]){
if (i == ip){
continue;
}
int v = u ^ a[i].u ^ a[i].v;
if (time_in[v] == 0){
dfs_time(v, i);
low[u] = min(low[u], low[v]);
}
else{
low[u] = min(low[u], time_in[v]);
}
}
if (low[u] == time_in[u] and ip != -1){
bridge[ip] = true;
}
}
int cnt_cpn;
int to_cpn[N];
vector <int> cpn_color[N];
int cnt_edge;
edge a2[N];
int a2_to_a[N];
vector <int> adj2[N];
vector <int> sources;
int sz[N];
int ctrtour, tour[N], tin[N], tout[N];
void dfs_tour(int u, int ip = -1){
tour[++ctrtour] = u;
tin[u] = ctrtour;
sz[u] = (int)cpn_color[u].size();
for (auto i: adj2[u]){
if (i == ip){
continue;
}
int v = u ^ a2[i].u ^ a2[i].v;
dfs_tour(v, i);
sz[u] += sz[v];
}
tout[u] = ctrtour;
}
int ans[N];
void dfs_component(int u, int delta, counter& DS, int ip = -1){
if (delta == 1){
for (auto col: cpn_color[u]){
DS.insert(col);
}
}
else{
for (auto col: cpn_color[u]){
DS.erase(col);
}
}
for (auto i: adj2[u]){
if (i == ip){
continue;
}
int v = u ^ a2[i].u ^ a2[i].v;
dfs_component(v, delta, DS, i);
}
}
void dfs_mergeset(int u, int ip = -1, bool keep = false){
int heavy = -1;
for (auto i: adj2[u]){
if (i == ip){
continue;
}
int v = u ^ a2[i].u ^ a2[i].v;
if (heavy == -1 or sz[v] > sz[heavy]){
heavy = v;
}
}
for (auto i: adj2[u]){
if (i == ip){
continue;
}
int v = u ^ a2[i].u ^ a2[i].v;
if (v != heavy){
dfs_mergeset(v, i);
}
}
for (auto i: adj2[u]){
if (i == ip){
continue;
}
int v = u ^ a2[i].u ^ a2[i].v;
if (v == heavy){
dfs_mergeset(v, i, true);
}
}
for (auto col: cpn_color[u]){
DSout.erase(col);
DSin.insert(col);
}
for (auto i: adj2[u]){
if (i == ip){
continue;
}
int v = u ^ a2[i].u ^ a2[i].v;
if (v != heavy){
for (int t = tin[v]; t <= tout[v]; t++){
int node = tour[t];
for (auto col: cpn_color[node]){
DSout.erase(col);
DSin.insert(col);
}
}
}
}
if (ip != -1){
ans[a2_to_a[ip]] = ans[a2_to_a[ip]] - DS.ans + DSout.ans + DSin.ans;
}
if (not keep){
for (int t = tin[u]; t <= tout[u]; t++){
int node = tour[t];
for (auto col: cpn_color[node]){
DSin.erase(col);
DSout.insert(col);
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
int tests; cin >> tests; while (tests--){
cin >> n >> m;
ForE(u, 1, n){
cin >> color[u];
}
ForE(u, 1, n){
adj[u].clear();
}
ForE(i, 1, m){
int u, v;
cin >> u >> v;
a[i] = edge{u, v};
adj[u].emplace_back(i);
adj[v].emplace_back(i);
}
ctrtime = 0;
ForE(u, 1, n){
time_in[u] = 0;
low[u] = 0;
}
ForE(i, 1, m){
bridge[i] = false;
}
ForE(u, 1, n){
if (time_in[u] == 0){
dfs_time(u);
}
}
dsu.reset(n + 1);
cnt_cpn = 0;
ForE(i, 1, m){
if (not bridge[i]){
dsu.merge(a[i].u, a[i].v);
}
}
ForE(u, 1, n){
if (dsu.root(u) == u){
to_cpn[u] = ++cnt_cpn;
}
}
cnt_edge = 0;
ForE(x, 1, cnt_cpn){
cpn_color[x].clear();
adj2[x].clear();
}
ForE(u, 1, n){
to_cpn[u] = to_cpn[dsu.root(u)];
cpn_color[to_cpn[u]].emplace_back(color[u]);
}
ForE(i, 1, m){
if (bridge[i]){
int x = to_cpn[a[i].u], y = to_cpn[a[i].v];
a2[++cnt_edge] = edge{x, y};
a2_to_a[cnt_edge] = i;
adj2[x].emplace_back(cnt_edge);
adj2[y].emplace_back(cnt_edge);
}
}
sources.clear();
ctrtour = 0;
ForE(x, 1, cnt_cpn){
tour[x] = 0;
tin[x] = 0;
tout[x] = 0;
}
ForE(x, 1, cnt_cpn){
if (tin[x] == 0){
sources.emplace_back(x);
dfs_tour(x);
}
}
ans[1] = 0;
for (auto x: sources){
dfs_component(x, 1, DS);
ans[1] += DS.ans;
dfs_component(x, -1, DS);
}
ForE(i, 2, m){
ans[i] = ans[i - 1];
}
for (auto x: sources){
dfs_component(x, 1, DS);
dfs_component(x, 1, DSout);
dfs_mergeset(x);
dfs_component(x, -1, DS);
dfs_component(x, -1, DSout);
}
ForE(i, 1, m){
cout << ans[i] << " \n"[i == m];
}
}
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 15992kb
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: 586ms
memory: 34152kb
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: 330ms
memory: 33976kb
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: 321ms
memory: 34032kb
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: 393ms
memory: 28144kb
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: 386ms
memory: 28352kb
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: 387ms
memory: 26848kb
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: 384ms
memory: 27740kb
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