UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212883#3821. T3drdilyor203542ms629116kbC++115.7kb2024-10-20 18:04:112024-10-20 18:51:23

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int n,m;
int a[1000005];
vector<pair<int,int>> e[2000005];
//Two meows, both alike in dignity,
//in fair Verona, where we lay our scene.
//From ancient grudge break to new mutiny,
//where civil blood make civil hands unclean.
int ans[2000005];
int s[2000005];
int c[2000005];
int l;
bool v[2000005];
void chk(int x){
	v[x]=1;s[++l]=a[x];
	for(auto it:e[x]){
		int to=it.first,id=it.second;
		if(!v[to])chk(to);
	}
}
int cnt,len;
int mx[2000005];
bool cut[2000005];
int dfn[2000005],low[2000005];
map<pair<int,int>,int> wp;
void dfs(int x,int f){
	dfn[x]=low[x]=++cnt;
	for(auto it:e[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		if(!dfn[to]){
			s[++l]=id,dfs(to,x),low[x]=min(low[x],low[to]);
			if(low[to]>dfn[x]&&wp[{x,to}]==1&&x!=to)cut[id]=1;
		}
		else low[x]=min(low[x],dfn[to]);
	}
	//cout<<x<<" "<<low[x]<<" "<<dfn[x]<<"\n";
}
int bel[2000005];
void dfs2(int x){
	v[x]=1;bel[x]=len;
	s[++l]=a[x];
	for(auto it:e[x]){
		int to=it.first,id=it.second;
		if(v[to])continue;
		if(cut[id])continue;
		dfs2(to);
	}
}
vector<pair<int,int>> info[2000005];
int x[2000005],y[2000005];
vector<pair<int,int>> g[2000005];
int sz[2000005],hs[2000005];
void dfs_init(int x,int f){
	sz[x]=1;hs[x]=-1;v[x]=1;
	for(auto it:g[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		dfs_init(to,x);
		sz[x]+=sz[to];
		if(hs[x]==-1||sz[to]>sz[hs[x]])hs[x]=to;
	}
}
int cl[2000005];
multiset<int> st;
int dq[2000005];
int tp;
void ins(int x){
	//cout<<"ins "<<x<<"\n";
	dq[++tp]=x;
	//return;
	for(auto v:info[x]){
		int key=v.first,val=v.second;
		if(cl[key])st.erase(st.lower_bound(cl[key]));
		cl[key]+=val;
		if(cl[key])st.insert(cl[key]);
	}
}
void del(int x){
	//cout<<"del "<<x<<"\n";
	//return;
	for(auto v:info[x]){
		int key=v.first,val=v.second;
		if(cl[key])st.erase(st.lower_bound(cl[key]));
		cl[key]-=val;
		if(cl[key])st.insert(cl[key]);
	}
}
void clear(){
	while(tp){
		del(dq[tp]),tp--;
	}
}
bool added[2000005];
void wcz(int x,int f,int fp){
	int eid=-1;
	for(auto it:g[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		if(to==hs[x]){eid=id;continue;}
		wcz(to,x,id);clear();
	}
	if(hs[x]!=-1)wcz(hs[x],x,eid);
	for(auto it:g[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		if(to==hs[x])continue;
		wcz(to,x,id);
	}
	ins(x);
	if(fp&&!added[fp]){
		//if(fp==2){
		//	cout<<"G"<<*(--st.end())<<" "<<*st.begin()<<"\n";
		//}
		added[fp]=1;
		ans[fp]+=(st.empty()?0ll:*(--st.end()));
		//cout<<fp<<"+="<<(st.empty()?0ll:*(--st.end()))<<"\n";
	}
}
void add2(int x){
	//cout<<"ins "<<x<<"\n";
	//return;
	for(auto v:info[x]){
		int key=v.first,val=v.second;
		if(cl[key])st.erase(st.lower_bound(cl[key]));
		cl[key]+=val;
		if(cl[key])st.insert(cl[key]);
	}
}
void del2(int x,int fl=1){
	if(fl)dq[++tp]=x;
	//cout<<"del "<<x<<"\n";
	//return;
	for(auto v:info[x]){
		int key=v.first,val=v.second;
		if(cl[key])st.erase(st.lower_bound(cl[key]));
		cl[key]-=val;
		if(cl[key])st.insert(cl[key]);
	}
}
void clear2(){
	while(tp){
		add2(dq[tp]),tp--;
	}
}
int lol;
vector<int> al;
void dfs_init2(int x,int f){
	add2(x);lol++;al.push_back(x);
	for(auto it:g[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		dfs_init2(to,x);
	}
}
bool added2[2000005];
void wyn(int x,int f,int fp){
	int eid=-1;
	for(auto it:g[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		if(to==hs[x]){eid=id;continue;}
		wyn(to,x,id);clear2();
	}
	if(hs[x]!=-1)wyn(hs[x],x,eid);
	for(auto it:g[x]){
		int to=it.first,id=it.second;
		if(to==f)continue;
		if(to==hs[x])continue;
		wyn(to,x,id);
	}
	del2(x);
	if(fp&&!added2[fp]){
		added2[fp]=1;
		ans[fp]+=(st.empty()?0ll:*(--st.end()));
		//cout<<fp<<"+="<<(st.empty()?0ll:*(--st.end()))<<"\n";
	}
}
signed main(){
	//freopen("ex_color4.in","r",stdin);
	//freopen("ex_color4.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();x[i]=u,y[i]=v;
		wp[{u,v}]++,wp[{v,u}]++;
		e[u].push_back({v,i});
		e[v].push_back({u,i});
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		if(!v[i]){
			l=0,chk(i);
			for(int j=1;j<=l;j++)c[s[j]]++;
			for(int j=1;j<=l;j++)mx[i]=max(mx[i],c[s[j]]);
			tot+=mx[i];
			//cout<<mx[i]<<"\n";
			for(int j=1;j<=l;j++)c[s[j]]--;
		}
	}
	for(int i=1;i<=n;i++)v[i]=0;
	for(int i=1;i<=m;i++)ans[i]=tot;
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			l=0;
			dfs(i,0);
			for(int j=1;j<=l;j++)if(cut[s[j]])ans[s[j]]-=mx[i];
			//cout<<"\n";
		}
	}
	for(int i=1;i<=n;i++){
		if(!v[i]){
			l=0,++len;
			dfs2(i);
			vector<pair<int,int>> tmp;
			for(int j=1;j<=l;j++)c[s[j]]++;
			for(int j=1;j<=l;j++){
				if(c[s[j]])tmp.push_back({s[j],c[s[j]]}),c[s[j]]=0;
			}
			info[len]=tmp;
		}
	}
	//3 2
	//2 1
	//4 1
	for(int i=1;i<=n;i++)v[i]=0;
	for(int i=1;i<=m;i++){
		if(cut[i]){
			//cout<<bel[x[i]]<<" "<<bel[y[i]]<<"\n";
			g[bel[x[i]]].push_back({bel[y[i]],i});
			g[bel[y[i]]].push_back({bel[x[i]],i});
		}
	}
	//cout<<ans[2]<<"\n";
	for(int i=1;i<=len;i++){
		if(!v[i]){
			tp=0;
			st.clear();
			dfs_init(i,0);
			wcz(i,0,0);
			clear();tp=0,st.clear();lol=0;al.clear();
			//cout<<ans[10]<<"\n";
			dfs_init2(i,0);
			wyn(i,0,0);
			//cout<<tp<<" "<<lol<<"\n";
			clear2();
			for(auto it:al)del2(it,0);
		}
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
	return 0;
}
//look at my code
//my code is amazing

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 17ms
memory: 146584kb

input:

1000 1000
127389 742557 379975 792810 941035 343277 900097 363092 558167 425747 665153 303524 127389...

output:

165 164 164 165 164 164 164 164 164 165 165 164 165 164 164 164 164 165 165 165 165 164 165 165 164 ...

result:

ok 1000 numbers

Test #2:

score: 0
Time Limit Exceeded

input:

1000000 1000000
1 10 5 5 1 5 10 1 1 7 1 4 6 5 1 8 5 9 1 10 7 1 1 9 6 6 6 3 9 4 1 5 6 6 9 2 4 6 5 2 1...

output:


result:


Test #3:

score: 0
Time Limit Exceeded

input:

1000000 1000000
4 8 3 10 6 5 2 1 1 5 5 4 10 6 3 3 3 1 5 8 8 8 3 1 4 1 9 5 6 9 4 5 1 2 7 10 8 3 5 3 5...

output:


result:


Test #4:

score: 10
Accepted
time: 3525ms
memory: 629116kb

input:

1000000 999999
459788 891071 867951 861734 991468 169523 626206 72233 797362 681021 590377 119511 88...

output:

404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 404 ...

result:

ok 999999 numbers

Test #5:

score: 0
Time Limit Exceeded

input:

1000000 999999
80449 974907 433485 520089 585081 449526 106163 294162 453340 699909 512597 103883 63...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

1000000 999999
993172 569193 453215 859064 765172 926293 79502 468888 473832 139292 536558 66118 723...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

1000000 999999
483962 269691 318073 523931 943387 659724 757207 752838 973431 637496 211548 132948 9...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000000 999999
177974 461791 142691 363772 546626 904219 194179 141553 539237 278698 488828 454167 9...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

1000000 999999
511557 68848 896777 731815 32886 932833 390201 839100 548903 603989 235104 501625 206...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

1000000 999999
808476 306755 435706 912414 23416 659340 799407 8345 687388 935128 421729 38016 93583...

output:


result: