QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385973 | #6127. Kawa Exam | Guchenxi0971 | AC ✓ | 1012ms | 47216kb | C++14 | 4.6kb | 2024-04-11 10:40:57 | 2024-04-11 10:40:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int Max=2e5+10;
struct Node{
int to,next,u,id;
Node(int to=0,int next=0,int u=0,int id=0):
to(to),next(next),u(u),id(id){;}
}a[Max<<1],B[Max<<1];
int head[Max],cnt=0;
void add(int x,int y,int id){
a[++cnt]=Node(y,head[x],x,id);
head[x]=cnt;
}
int Cnt=1;
void Add(int x,int y,int id){
B[++Cnt]=Node(y,head[x],x,id);
head[x]=Cnt;
}
struct Tree{
int fa,siz,son,top,l,r,id;
#define siz(x) b[x].siz
#define son(x) b[x].son
#define top(x) b[x].top
#define fa(x) b[x].fa
#define id(x) b[x].id
#define l(x) b[x].l
#define r(x) b[x].r
}b[Max];
void dfs1(int now,int fa){
fa(now)=fa;
siz(now)=1;
l(now)=0;
son(now)=0;
for(int i=head[now];i;i=a[i].next){
int to=a[i].to;
if(to!=fa){
dfs1(to,now);
siz(now)+=siz(to);
son(now)=siz(son(now))>siz(to)?son(now):to;
}
}
}
int Res=0;
void dfs2(int now,int top){
top(now)=top;
l(now)=++Res;
id(Res)=now;
if(son(now)){
dfs2(son(now),top);
}
for(int i=head[now];i;i=a[i].next){
int to=a[i].to;
if(!l(to))dfs2(to,to);
}
r(now)=Res;
}
int Sum[Max],NumSum[Max],Pos[Max],NumPos[Max],MaxSum,MaxPos;
vector<int>Val[Max];
int res[Max];
/*
Sum表示这个颜色有几个
NumSum[i]表示Sum[j]为i的j有几个
MaxSum表示最大的Sum[i]
Sum为当前子树内部的节点信息
Pos同理
Pos为子树外的节点信息
*/
void WorkSum(int val,int sum){
if(sum==1){
NumSum[Sum[val]]--;
if(MaxSum==Sum[val])MaxSum++;
Sum[val]++;
NumSum[Sum[val]]++;
}else{
NumSum[Sum[val]]--;
Sum[val]--;
NumSum[Sum[val]]++;
if(!NumSum[MaxSum])MaxSum--;
}
}
void WorkPos(int val,int sum){
if(sum==1){
NumPos[Pos[val]]--;
if(MaxPos==Pos[val])MaxPos++;
Pos[val]++;
NumPos[Pos[val]]++;
}else{
NumPos[Pos[val]]--;
Pos[val]--;
NumPos[Pos[val]]++;
if(!NumPos[MaxPos])MaxPos--;
}
}
int skp;
void Work(int now,int z){
for(int i=l(now);i<=r(now);++i){
if(id(i)==skp){
i=r(id(i));
continue;
}
for(int j:Val[id(i)]){
WorkSum(j,1*z);
WorkPos(j,-1*z);
}
}
}
int Vis[Max];
void Dsu(int now,int id,int K){
Vis[now]=1;
int RRR=0;
for(int i=head[now];i;i=a[i].next){
int to=a[i].to;
if(to==son(now))RRR=a[i].id;
if(to==fa(now)||to==son(now))continue;
Dsu(to,a[i].id,K);
}
if(son(now)){
Dsu(son(now),RRR,K);
skp=son(now);
}
Work(now,1);
res[id]=MaxSum+MaxPos-K;
if(now==top(now)){
skp=0;
Work(now,-1);
}
}
int low[Max],dfn[Max];
vector<vector<int> > ans;
int Sta[Max],opt;
void Work(int now){
vector<int>s;
for(int i=0;i!=now;){
s.push_back(i=Sta[opt--]);
}
ans.push_back(s);
}
int pos=0;
void dfs(int now,int z){
low[now]=dfn[now]=++pos;
Sta[++opt]=now;
for(int i=head[now];i;i=B[i].next){
int to=B[i].to;
if(i==(z^1))continue;
if(!dfn[to]){
dfs(to,i);
low[now]=min(low[now],low[to]);
if(low[to]>dfn[now])Work(to);
}else{
low[now]=min(low[now],dfn[to]);
}
}
}
int val[Max],fa[Max];
void dfs3(int now,int opt){
if(opt) for(int j:Val[now]) WorkPos(j,1);//cout << j << ' ';
else for(int j:Val[now])WorkPos(j,-1);
for(int i=head[now];i;i=a[i].next){
int to=a[i].to;
if(to!=fa(now))dfs3(to,opt);
}
}
void Clear(){
memset(head,0,sizeof(head));
memset(Vis,0,sizeof(Vis));
memset(res,0,sizeof(res));
memset(dfn,0,sizeof(dfn));
// memset(Sta,0,sizeof(Sta));
ans.clear();
skp=opt=pos=Res=MaxPos=MaxSum=0;
Cnt=1;
cnt=0;
}
void work(){
Clear();
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&val[i]);
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
Add(x,y,i);
Add(y,x,i);
}
for(int i=1;i<=n;++i){
if(!dfn[i]){
dfs(i,0);
Work(i);
}
}
int pos=n;
memset(head,0,sizeof(head));
for(auto S:ans){
++pos;
Val[pos].clear();
for(int i:S){
fa[i]=pos;
Val[pos].push_back(val[i]);
}
}
for(int i=2;i<=Cnt;i+=2){
int to=B[i].to;
int u=B[i].u;
if(fa[to]!=fa[u]){
add(fa[to],fa[u],B[i].id);
add(fa[u],fa[to],B[i].id);
}
}
NumPos[0]=NumSum[0]=INT_MAX;
int R=0;
for(int i=n+1;i<=pos;++i){
if(!Vis[i]){
dfs1(i,0);
dfs2(i,i);
dfs3(i,1);
R+=MaxPos;
Dsu(i,0,MaxPos);
dfs3(i,0);
}
}
for(int i=1;i<=m;++i){
cout << res[i]+R;
if(i!=m)putchar(' ');
}
}
signed main(){
int T;
scanf("%d",&T);
while(T--){
work();
if(T)cout << "\n";
}
return 0;
}
/*
通过给定的边建图,边双缩点,必定形成森林。
对于每棵树dsu on tree。
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 29960kb
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: 1012ms
memory: 47216kb
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: 332ms
memory: 44216kb
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: 326ms
memory: 44072kb
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: 378ms
memory: 44496kb
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: 357ms
memory: 43708kb
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: 377ms
memory: 43424kb
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: 366ms
memory: 43436kb
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