QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91835 | #6127. Kawa Exam | zhouhuanyi | ML | 4ms | 22096kb | C++23 | 5.6kb | 2023-03-29 18:02:12 | 2023-03-29 18:02:14 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#define N 100000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int l,r;
bool operator < (const reads &t)const
{
return l<t.l;
}
};
reads tongs[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>ET[N+1];
int T,n,m,rst,res,lengths,lg[N+1],a[N+1],X[N+1],Y[N+1],cl[N+1],depth[N+1],fa[N+1][21],cater,leng,lengs,tong[N+1],length,dque[N+1],top,dfn[N+1],low[N+1],dfns[N+1],sz[N+1],belong[N+1],q[N+1],cnt[N+1],A[N+1],B[N+1],ST[N+1][21],ans[N+1];
bool used[N+1];
stack<int>p;
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void add2(int x,int y)
{
ES[x].push_back(y),ES[y].push_back(x);
return;
}
void tarjan(int x,int y)
{
dfn[x]=low[x]=++leng,p.push(x);
for (int i=0;i<E[x].size();++i)
{
if (!dfn[E[x][i]])
{
tarjan(E[x][i],x),low[x]=min(low[x],low[E[x][i]]);
if (low[E[x][i]]>dfn[x])
{
++cater;
while (p.top()!=E[x][i]) belong[p.top()]=cater,p.pop();
belong[p.top()]=cater,p.pop();
}
}
else if (E[x][i]!=y) low[x]=min(low[x],dfn[E[x][i]]);
}
return;
}
void dfs(int x)
{
used[x]=1,dfns[x]=++lengs,sz[x]=1;
for (int i=0;i<ES[x].size();++i)
if (!used[ES[x][i]])
cl[ES[x][i]]=cl[x],depth[ES[x][i]]=depth[x]+1,dfs(ES[x][i]),sz[x]+=sz[ES[x][i]];
return;
}
bool cmp(int x,int y)
{
return a[x]<a[y];
}
bool cmp2(int x,int y)
{
return dfns[x]<dfns[y];
}
bool LENG(int x,int y)
{
if (!x) return 1;
return dfns[x]<=dfns[y]&&dfns[y]<=dfns[x]+sz[x]-1;
}
int lca(int x,int y)
{
if (depth[x]<depth[y]) swap(x,y);
for (int i=lg[n];i>=0;--i)
if (depth[fa[x][i]]>=depth[y])
x=fa[x][i];
if (x==y) return x;
for (int i=lg[n];i>=0;--i)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int tfa(int x,int y)
{
for (int i=lg[n];i>=0;--i)
if (depth[fa[x][i]]>depth[y])
x=fa[x][i];
return x;
}
void dfs2(int x)
{
for (int i=0;i<ET[x].size();++i) dfs2(ET[x][i]),cnt[x]+=cnt[ET[x][i]];
A[x]=max(A[x],cnt[x]);
return;
}
void solve(int l,int r,int d)
{
if (l>r) return;
int lw=lg[r-l+1];
ST[l][lw]=max(ST[l][lw],d),ST[r-(1<<lw)+1][lw]=max(ST[r-(1<<lw)+1][lw],d);
return;
}
void dfs3(int x,int d)
{
for (int i=0;i<ET[x].size();++i)
{
if (!x) dfs3(ET[x][i],cnt[ET[x][i]]);
else B[ET[x][i]]=max(B[ET[x][i]],d-cnt[ET[x][i]]),dfs3(ET[x][i],d);
}
if (x)
{
lengths=0;
for (int i=0;i<ET[x].size();++i) tongs[++lengths]=(reads){dfns[ET[x][i]],dfns[ET[x][i]]+sz[ET[x][i]]-1};
sort(tongs+1,tongs+lengths+1);
if (!lengths) solve(dfns[x]+1,dfns[x]+sz[x]-1,d);
else
{
solve(dfns[x]+1,tongs[1].l-1,d);
for (int i=2;i<=lengths;++i) solve(tongs[i-1].r+1,tongs[i].l-1,d);
solve(tongs[lengths].r+1,dfns[x]+sz[x]-1,d);
}
}
return;
}
void dfs4(int x)
{
used[x]=1,B[x]=max(B[x],ST[dfns[x]][0]);
for (int i=0;i<ES[x].size();++i)
if (!used[ES[x][i]])
B[ES[x][i]]=max(B[ES[x][i]],B[x]),dfs4(ES[x][i]),A[x]=max(A[x],A[ES[x][i]]);
return;
}
int main()
{
int ps,d,ds;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
T=read();
while (T--)
{
n=read(),m=read(),cater=leng=lengs=res=0,ps=1;
for (int i=1;i<=n;++i) a[i]=read(),dfn[i]=used[i]=fa[i][0]=A[i]=B[i]=0,E[i].clear(),ES[i].clear(),q[i]=i,A[i]=B[i]=0;
for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),add(X[i],Y[i]);
for (int i=1;i<=n;++i)
if (!dfn[i])
{
tarjan(i,0),++cater;
while (p.top()!=i) belong[p.top()]=cater,p.pop();
belong[p.top()]=cater,p.pop();
}
for (int i=1;i<=m;++i)
if (belong[X[i]]!=belong[Y[i]])
add2(belong[X[i]],belong[Y[i]]);
for (int i=1;i<=cater;++i) used[i]=0;
depth[1]=1;
for (int i=1;i<=cater;++i)
if (!used[i])
cl[i]=i,dfs(i);
for (int i=1;i<=lg[cater];++i)
for (int j=1;j<=cater;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
for (int i=0;i<=lg[cater];++i)
for (int j=1;j+(1<<i)-1<=cater;++j)
ST[j][i]=0;
sort(q+1,q+n+1,cmp);
for (int i=1;i<=n;++i)
if (i==n||a[q[i]]!=a[q[i+1]])
{
length=top=0;
for (int j=ps;j<=i;++j) tong[++length]=belong[q[j]],ET[belong[q[j]]].clear(),cnt[belong[q[j]]]=0;
sort(tong+1,tong+length+1,cmp2),length=unique(tong+1,tong+length+1)-tong-1;
for (int j=1;j<=length;++j)
{
d=0;
while (top&&!LENG(dque[top],tong[j]))
{
if (d) ET[dque[top]].push_back(d);
d=dque[top],top--;
}
if (d)
{
ds=lca(d,tong[j]);
if (!top||ds!=dque[top]) ET[ds].clear(),ET[ds].push_back(d),cnt[ds]=0,dque[++top]=ds;
}
dque[++top]=tong[j];
}
for (int j=2;j<=top;++j) ET[dque[j-1]].push_back(dque[j]);
for (int j=ps;j<=i;++j) cnt[belong[q[j]]]++;
rst=i-ps+1,dfs2(dque[1]),dfs3(dque[1],0),ps=i+1;
}
for (int i=lg[cater];i>=1;--i)
for (int j=1;j+(1<<i)-1<=cater;++j)
ST[j][i-1]=max(ST[j][i-1],ST[j][i]),ST[j+(1<<(i-1))][i-1]=max(ST[j+(1<<(i-1))][i-1],ST[j][i]);
for (int i=1;i<=cater;++i) used[i]=0;
for (int i=1;i<=cater;++i)
if (!used[i])
dfs4(i),res+=A[i];
for (int i=1;i<=m;++i)
{
if (belong[X[i]]==belong[Y[i]]) ans[i]=res;
else
{
if (depth[belong[X[i]]]>depth[belong[Y[i]]]) swap(X[i],Y[i]);
ans[i]=res+A[belong[Y[i]]]+B[belong[Y[i]]]-A[cl[belong[Y[i]]]];
}
}
for (int i=1;i<=m-1;++i) printf("%d ",ans[i]);
printf("%d\n",ans[m]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 22096kb
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: -100
Memory Limit Exceeded
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...