QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648320 | #6127. Kawa Exam | atgc | RE | 3ms | 13848kb | C++23 | 3.6kb | 2024-10-17 18:24:36 | 2024-10-17 18:24:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct{
int cnt_v[maxn];
vector<int>cis[maxn];
int val,cnt;
void push(int x){
cis[++cnt_v[x]].push_back(x);
if(cnt_v[x]>cnt)cnt=cnt_v[val=x];
}
void pop(int x){
cis[--cnt_v[x]].push_back(x);
if(val==x){
while(!cis[cnt].empty()&&cnt_v[cis[cnt].back()]!=cnt)
cis[cnt].pop_back();
if(cis[cnt].empty())--cnt;
else val=cis[cnt].back();
}
}
void clear(){
for(int i=1;i<=cnt;++i){
for(int x:cis[i])cnt_v[x]=0;
// cis[i].swap({});
// cis[i]={};
vector<int>().swap(cis[i]);
}
val=cnt=0;
}
}qcommon;
int n,m,va[maxn],fa[maxn];
vector<int>a[maxn],suba[maxn];
struct{int nxt,v;}edge[maxn<<1];
int head[maxn],ec;
void add(int u,int v){edge[++ec]={head[u],v};head[u]=ec;}
int dfn[maxn],low[maxn],dfc,bc,c[maxn],dfu[maxn];
static int s[maxn],tp;
void dfs(int u,int in){
// infun(u);
dfu[dfn[s[++tp]=u]=low[u]=++dfc]=u;
for(int i=head[u];i;i=edge[i].nxt){
if(i==in)continue;
int v=edge[i].v;
if(!dfn[v])dfs(v,i^1),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]&&++bc)while(s[tp+1]!=u)a[bc].push_back(va[s[tp]]),c[s[tp--]]=bc;
}
vector<int>G[maxn];
int siz[maxn],son[maxn];
void cal_son(int u,int fa){
::fa[u]=fa;
siz[u]=a[u].size();son[u]=0;
for(int v:G[u])if(v!=fa){
cal_son(v,u);
if(siz[son[u]]<siz[v])son[u]=v;
}
}
int cnt_sub[maxn],cnt_out[maxn];
void dfs_sub(int u,int fa){
// infun(u,fa,a[u],son[u]);
for(int v:G[u])if(v!=fa&&v!=son[u]){
dfs_sub(v,u);qcommon.clear();
}
suba[u]=a[u];
if(son[u]){
dfs_sub(son[u],u);
for(int va:a[u])suba[son[u]].push_back(va);
vector<int>().swap(suba[u]);swap(suba[u],suba[son[u]]);
}
// deb(suba[u],a[u]);
for(int v:a[u])qcommon.push(v);
// deb(qcommon.cnt);
for(int v:G[u])if(v!=fa&&v!=son[u])for(int va:suba[v])qcommon.push(va);
cnt_sub[u]=qcommon.cnt;
// deb(cnt_sub[u]);
}
void dfs_out(int u,int fa){//when dfs end, push all
cnt_out[u]=qcommon.cnt;
// infun(u,fa,cnt_out[u]);
for(int va:a[u])qcommon.push(va);
for(int v:G[u])if(v!=fa&&v!=son[u]){
for(int va:suba[v])qcommon.push(va);
}
if(son[u])dfs_out(son[u],u);
for(int v:G[u])if(v!=fa&&v!=son[u]){
for(int va:suba[v])qcommon.pop(va);
dfs_out(v,u);
}
}
int ans,ansdta[maxn];
void sol(){
cin>>n>>m;
#define cls(a) memset(a+1,0,n*sizeof a[0])
cls(head),cls(dfn),cls(low),cls(c);dfc=bc=ans=0;ec=1;tp=0;
memset(ansdta+1,0,m*sizeof ansdta[0]);
for(int i=1;i<=n;++i)cin>>va[i],a[i].clear(),G[i].clear();
for(int i=1,u,v;i<=m;++i)cin>>u>>v,add(u,v),add(v,u);
for(int u=1;u<=n;++u)
if(!dfn[u]){
int pdfc=dfc;
int pbc=bc;
dfs(u,0);
int CC=0;
set<pair<int,int>>ES;
for(int i=pdfc+1;i<=dfc;++i){
int u=dfu[i];
for(int i=head[u];i;i=edge[i].nxt)
if(int v=edge[i].v;c[u]!=c[v]){
// deb(u,v,c[u],c[v]);
if(ES.count({c[u],c[v]}))continue;
ES.insert({c[u],c[v]});
G[c[u]].push_back(c[v]);
++CC;
}
}
// deb(dfc,pdfc,CC);
assert(CC==(bc-pbc-1)*2);
cal_son(u,0);
dfs_sub(u,0);qcommon.clear();
dfs_out(u,0);qcommon.clear();
int vv=cnt_sub[u];
ans+=cnt_sub[u];
for(int i=pdfc+1;i<=dfc;++i){
int u=dfu[i];
for(int i=head[u];i;i=edge[i].nxt)
if(int v=edge[i].v;c[u]!=c[v]) {
// deb(i,c[u],c[v]);
if(fa[c[u]]==c[v])ansdta[i>>1]=cnt_out[c[u]]+cnt_sub[c[u]]-vv;
else ansdta[i>>1]=cnt_out[c[v]]+cnt_sub[c[v]]-vv;
}
}
}
for(int i=1;i<=m;++i)
cout<<ans+ansdta[i]<<" \n"[i==m];
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0);
int T;cin>>T;while(T--)sol();
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13848kb
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
Runtime Error
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...