QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#533397 | #6127. Kawa Exam | EricQian | ML | 3ms | 30604kb | C++14 | 5.3kb | 2024-08-25 21:56:09 | 2024-08-25 21:56:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pa pair<int,int>
#define fi first
#define se second
typedef long long ll;
#define Maxn 200005
inline int rd()
{
int x=0;
char ch,t=0;
while(!isdigit(ch = getchar())) t|=ch=='-';
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return t?-x:x;
}
double StartTime;
int n,m,tot,ans,Time,tp,All;
int dfn[Maxn],low[Maxn],sta[Maxn],bel[Maxn],BELlian[Maxn],lianans[Maxn],a[Maxn];
int hea[Maxn],nex[Maxn<<1],ver[Maxn<<1],num[Maxn<<1];
bool edg[Maxn<<1];
bool ins[Maxn],vis[Maxn];
int OUTput[Maxn];
int uu[Maxn],vv[Maxn];
int cnt[Maxn];
int siz[Maxn],bigson[Maxn];
vector<pa> T[Maxn],hav[Maxn];
vector<int> cur;
map<pa,int> mp;
struct TREE
{
int tree[Maxn<<2];
void build(int p,int nl,int nr)
{
tree[p]=0;
if(nl==nr) return;
int mid=(nl+nr)>>1;
build(p<<1,nl,mid),build(p<<1|1,mid+1,nr);
}
void add(int p,int nl,int nr,int x,int k)
{
if(nl==nr) { tree[p]+=k; return; }
int mid=(nl+nr)>>1;
if(x<=mid) add(p<<1,nl,mid,x,k);
else add(p<<1|1,mid+1,nr,x,k);
tree[p]=max(tree[p<<1],tree[p<<1|1]);
}
int query(int p,int nl,int nr,int x)
{
if(nl==nr) return tree[p];
int mid=(nl+nr)>>1;
if(x<=mid) return query(p<<1,nl,mid,x);
else return query(p<<1|1,mid+1,nr,x);
}
};
TREE cntup,cntdown;
inline void add(int x,int y,int d)
{ ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=false,num[tot]=d; }
void tarjan(int x,int fa)
{
dfn[x]=low[x]=++Time,sta[++tp]=x,ins[x]=true;
for(int i=hea[x];i;i=nex[i])
{
if(!dfn[ver[i]]) tarjan(ver[i],x),low[x]=min(low[x],low[ver[i]]);
else if(ins[ver[i]] && ver[i]!=fa) low[x]=min(low[x],dfn[ver[i]]);
if(low[ver[i]]>dfn[x]) // ???
{
edg[i]=edg[i^1]=true;
}
}
if(dfn[x]==low[x])
{
do
{
x=sta[tp],tp--,ins[x]=false;
} while (dfn[x]!=low[x]);
}
}
void dfs1(int x)
{
vis[x]=true;
cur.push_back(x);
cnt[a[x]]++;
bel[x]=All;
for(int i=hea[x];i;i=nex[i]) if(!edg[i] && !vis[ver[i]])
dfs1(ver[i]);
}
void dfs2(int x,int fa,int BEL)
{
siz[x]=1;
BELlian[x]=BEL,vis[x]=true;
for(pa v:hav[x]) cnt[v.first]+=v.second;
for(pa v:T[x]) if(v.first!=fa)
{
dfs2(v.first,x,BEL),siz[x]+=siz[v.first];
if(siz[v.first]>siz[bigson[x]]) bigson[x]=v.first;
}
}
void dfs3(int x,int fa)
{
for(pa v:hav[x])
lianans[BELlian[x]]=max(lianans[BELlian[x]],cnt[v.first]),
cnt[v.first]=0;
for(pa v:T[x]) if(v.first!=fa) dfs3(v.first,x);
}
inline void Erase(int x)
{
for(pa v:hav[x])
{
cntdown.add(1,1,100000,v.first,v.second);
cntup.add(1,1,100000,v.first,-v.second);
}
}
inline void Insert(int x)
{
for(pa v:hav[x])
{
cntdown.add(1,1,100000,v.first,-v.second);
cntup.add(1,1,100000,v.first,v.second);
}
}
void dfs5(int x,int fa)
{
for(pa v:hav[x]) cntdown.add(1,1,100000,v.first,v.second);
for(pa v:T[x]) if(v.first!=fa)
dfs5(v.first,x);
}
void dfs6(int x,int fa)
{
for(pa v:hav[x]) cntdown.add(1,1,100000,v.first,-v.second);
for(pa v:T[x]) if(v.first!=fa)
dfs6(v.first,x);
}
void dfs4(int x,int fa)
{
sta[++tp]=x,Insert(x);
for(pa v:T[x]) if(v.first!=fa) dfs4(v.first,x);
}
void solve(int x,int fa,int From)
{
vis[x]=true;
for(pa v:T[x]) if(v.first!=fa && v.first!=bigson[x])
{
int Intp=tp;
solve(v.first,x,v.second);
while(tp>Intp) Erase(sta[tp]),tp--;
}
for(pa v:T[x]) if(v.first==bigson[x]) { solve(bigson[x],x,v.second); break; }
for(pa v:T[x]) if(v.first!=fa && v.first!=bigson[x]) dfs4(v.first,x);
sta[++tp]=x,Insert(x);
if(From!=-1) OUTput[From]=ans-lianans[BELlian[x]]+(cntdown.tree[1]+cntup.tree[1]);
}
int main()
{
StartTime=clock();
// freopen("input.in","r",stdin);
//freopen(".out","w",stdout);
int Case=rd();
while(Case--)
{
mp.clear();
n=rd(),m=rd(),tot=1,ans=Time=All=tp=0;
for(int i=1;i<=n;i++) bel[i]=BELlian[i]=-1,vis[i]=false,bigson[i]=0,T[i].clear(),hav[i].clear();
for(int i=1;i<=n;i++) hea[i]=dfn[i]=0,T[i].clear(),ins[i]=false,lianans[i]=0;
for(int i=1;i<=n;i++) a[i]=rd();
for(int i=1;i<=m;i++)
{
uu[i]=rd(),vv[i]=rd();
if(uu[i]>vv[i]) swap(uu[i],vv[i]);
if(uu[i]!=vv[i]) add(uu[i],vv[i],i),add(vv[i],uu[i],i);
OUTput[i]=-1;
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
for(int i=1;i<=m;i++)
{
if(mp.count(pa(uu[i],vv[i])))
{
int tmp=mp[pa(uu[i],vv[i])];
edg[tmp*2]=edg[tmp*2+1]=0;
edg[i*2]=edg[i*2+1]=0;
}
mp[pa(uu[i],vv[i])]=i;
}
for(int i=1;i<=n;i++) if(!vis[i])
{
All++,dfs1(i);
for(int v:cur) if(cnt[a[v]]) hav[All].push_back(pa(a[v],cnt[a[v]])),cnt[a[v]]=0;
cur.clear();
}
for(int i=1;i<=n;i++)
for(int j=hea[i];j;j=nex[j]) if(edg[j])
T[bel[i]].emplace_back(bel[ver[j]],num[j]);
for(int i=1;i<=n;i++) vis[i]=false;
for(int i=1;i<=All;i++) if(!vis[i])
dfs2(i,0,i),dfs3(i,0),ans+=lianans[i];
for(int i=1;i<=All;i++) vis[i]=false;
for(int i=1;i<=All;i++) if(!vis[i])
{
dfs5(i,0),solve(i,0,-1);
while(tp) Erase(sta[tp]),tp--;
dfs6(i,0);
}
for(int i=1;i<=m;i++)
{
if(OUTput[i]==-1) printf("%d",ans);
else printf("%d",OUTput[i]);
if(i!=m) printf(" ");
else printf("\n");
}
}
//fclose(stdin);
//fclose(stdout);
#ifdef EricQian
printf("usetime %.0lf ms\n",clock()-StartTime);
#else
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 30604kb
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...