NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #212883 | #3821. T3 | drdilyor | 20 | 3542ms | 629116kb | C++11 | 5.7kb | 2024-10-20 18:04:11 | 2024-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...
