QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190224#6127. Kawa ExamZhou_JKAC ✓2833ms155640kbC++237.8kb2023-09-28 15:32:382023-09-28 15:32:38

Judging History

你现在查看的是最新测评结果

  • [2023-09-28 15:32:38]
  • 评测
  • 测评结果:AC
  • 用时:2833ms
  • 内存:155640kb
  • [2023-09-28 15:32:38]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int N=1000005;
int n,m,k;
int x[N],y[N],id[N];
int a[N];
struct Edge
{
    int to,next;
}edge[N<<1];
int head[N],cnt;
void add_edge(int u,int v)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
    return;
}
struct Segment_Tree_RMQ
{
    #define ls i*2
    #define rs i*2+1
    struct Node
    {
        int l,r;
        int mx; 
    }tree[N<<2];
    void push_up(int i)
    {
        tree[i].mx=max(tree[ls].mx,tree[rs].mx);
        return;
    }
    void build(int i,int l,int r)
    {
        tree[i].l=l,tree[i].r=r;
        if(l==r)
        {
            tree[i].mx=0;
            return;
        }
        int mid=(l+r)/2;
        build(ls,l,mid);
        build(rs,mid+1,r);
        return;
    }
    void modify(int i,int u,int v)
    {
        if(tree[i].l==tree[i].r)
        {
            tree[i].mx+=v;
            return;
        }
        if(u<=tree[ls].r) modify(ls,u,v);
        else modify(rs,u,v);
        push_up(i);
        return;
    }
    int query(int i,int l,int r)
    {
        if(l<=tree[i].l&&tree[i].r<=r) return tree[i].mx;
        int res=0;
        if(l<=tree[ls].r) res=max(res,query(ls,l,r));
        if(r>=tree[rs].l) res=max(res,query(rs,l,r));
//        if(i==1)cerr<<"query"<<l<<" "<<r<<" "<<res<<"\n"; 
        return res;
    }
    #undef ls
    #undef rs
}rmq;
struct Segment_Tree
{
    struct Node
    {
        int ls,rs;
        int mx1,mx2;
    }tree[N*25];
    int tot,rt[N];
    void clear()
    {
        tot=0;
        for(int i=1;i<=n;i++)
            rt[i]=0;
        return;
    }
    int new_node()
    {
        int now=++tot;
        tree[now].ls=tree[now].rs=0;
        tree[now].mx1=tree[now].mx2=0;
        return now;
    }
    void push_up(int i,int l,int r)
    {
        int mid=(l+r)/2;
        tree[i].mx1=max(tree[tree[i].ls].mx1,tree[tree[i].rs].mx1);
        tree[i].mx2=max(tree[i].ls?tree[tree[i].ls].mx2:rmq.query(1,l,mid),tree[i].rs?tree[tree[i].rs].mx2:rmq.query(1,mid+1,r));
        return;
    }
    void add(int &i,int l,int r,int u,int v)
    {
        if(!i)
        {
            i=new_node();
            if(l==r) tree[i].mx1=0,tree[i].mx2=rmq.query(1,l,r);
        }
        if(l==r)
        {
            tree[i].mx1+=v,tree[i].mx2-=v;
            return;
        }
        int mid=(l+r)/2;
        if(u<=mid) add(tree[i].ls,l,mid,u,v);
        else add(tree[i].rs,mid+1,r,u,v);
        push_up(i,l,r);
        return;
    }
    int merge(int u,int v,int l,int r)
    {
        if(!u) return v;
        if(!v) return u;
        if(l==r)
        {
            tree[u].mx1+=tree[v].mx1;
            tree[u].mx2-=rmq.query(1,l,r)-tree[v].mx2;
            return u;
        }
        int mid=(l+r)/2;
        tree[u].ls=merge(tree[u].ls,tree[v].ls,l,mid);
        tree[u].rs=merge(tree[u].rs,tree[v].rs,mid+1,r);
        push_up(u,l,r);
        return u;
    }
    int query_t1(int i,int l,int r,int L,int R)
    {
        if(!i) return 0;
        if(L<=l&&r<=R) return tree[i].mx1;
        int mid=(l+r)/2;
        if(R<=mid) return query_t1(tree[i].ls,l,mid,L,R);
        else if(L>mid) return query_t1(tree[i].rs,mid+1,r,L,R);
        else return max(query_t1(tree[i].ls,l,mid,L,R),query_t1(tree[i].rs,mid+1,r,L,R));
    }
    int query_t2(int i,int l,int r,int L,int R)
    {
        if(!i) return rmq.query(1,l,r);
        if(L<=l&&r<=R) return tree[i].mx2;
        int mid=(l+r)/2;
        if(R<=mid) return query_t2(tree[i].ls,l,mid,L,R);
        else if(L>mid) return query_t2(tree[i].rs,mid+1,r,L,R);
        else return max(query_t2(tree[i].ls,l,mid,L,R),query_t2(tree[i].rs,mid+1,r,L,R));
    }
}T;
int dfn[N],low[N],Index;
bool bridge[N];
void tarjan(int u,int prev)
{
    dfn[u]=low[u]=++Index;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) bridge[i]=bridge[i^1]=true;
        }
        else if(i!=(prev^1)) low[u]=min(low[u],dfn[v]);
    }
    return;
}
int bel[N],tot;
vector<int>block[N]; 
void dfs(int u)
{
    bel[u]=tot;
    block[tot].emplace_back(u);
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(bel[v]||bridge[i]) continue;
        dfs(v);
    }
    return;
}
vector<int>G[N];
map<pair<int,int>,int>vis;
void rebuild()
{
    fill(dfn+1,dfn+n+1,0);
    fill(low+1,low+n+1,0);
    for(int i=1;i<=cnt;i++)
        bridge[i]=false;
    Index=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,0);
//    for(int i=1;i<=m;i++)
//        cerr<<"bright"<<i<<" "<<int(bridge[id[i]])<<"\n";
    fill(bel+1,bel+n+1,0);
    tot=0;
    for(int i=1;i<=n;i++)
        block[i].clear();
    for(int i=1;i<=n;i++)
        if(!bel[i])
        {
            tot++;
            dfs(i);
        }
    for(int i=1;i<=tot;i++)
        G[i].clear();
//    cerr<<"tot"<<tot<<"\n";
    vis.clear();
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(bel[u]==bel[v]) continue;
            if(!vis.count({bel[u],bel[v]})) G[bel[u]].emplace_back(bel[v]),vis[{bel[u],bel[v]}]=1;
            else vis[{bel[u],bel[v]}]++;
//            cerr<<"add"<<bel[u]<<" "<<bel[v]<<"\n";
        }
    return;
}
int siz[N],dep[N];
vector<int>color;
void init(int u,int father)
{
    siz[u]=block[u].size();
    dep[u]=dep[father]+1;
    for(int v:G[u])
    {
        if(v==father) continue;
        init(v,u);
        siz[u]+=siz[v];
    }
    for(int t:block[u])
        color.emplace_back(a[t]);
    return;
}
int res[N];
int top[N];
void dfs(int u,int father,int topf)
{
    top[u]=topf;
    for(int v:G[u])
    {
        if(v==father) continue;
        dfs(v,u,topf);
        T.rt[u]=T.merge(T.rt[u],T.rt[v],1,k);
    }
//    cerr<<"now"<<u<<"\n";
    for(int t:block[u])
        T.add(T.rt[u],1,k,a[t],1);//cerr<<"add"<<t<<" "<<a[t]<<'\n';
    res[u]=T.query_t1(T.rt[u],1,k,1,k)+T.query_t2(T.rt[u],1,k,1,k);
//    cerr<<"res"<<u<<" "<<T.query_t1(T.rt[u],1,k,1,k)<<" "<<T.query_t2(T.rt[u],1,k,1,k)<<" res: "<<res[u]<<"\n"; 
    return;
}
int ans[N];
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    fill(head+1,head+n+1,0);
    cnt=1;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        add_edge(x[i],y[i]);
        add_edge(y[i],x[i]);
        id[i]=cnt;
    }
    k=*max_element(a+1,a+n+1);
    rebuild();
    rmq.build(1,1,k);
    long long sum=0;
    T.clear();
    fill(siz+1,siz+n+1,0); 
    for(int i=1;i<=tot;i++)
        if(!siz[i])
        {
            color.clear();
            init(i,0);
            for(int c:color)
                rmq.modify(1,c,1);
            dfs(i,0,i);
            sum+=res[i];
            for(int c:color)
                rmq.modify(1,c,-1);
//            cerr<<"done"<<i<<" "<<res[i]<<"\n";
        }
//    cerr<<"sum"<<sum<<"\n";
    for(int i=1;i<=m;i++)
        if(!bridge[id[i]]||vis[{x[i],y[i]}]>=2) ans[i]=sum;
        else
        {
//            cerr << "....." << i << "\n";
            if(dep[bel[x[i]]]<dep[bel[y[i]]]) swap(x[i],y[i]);
//            cerr<<"calc res"<<i<<" "<<x[i]<<" "<<res[x[i]]<<" "<<sum<<" "<<res[top[x[i]]]<<"\n";
            ans[i]=res[bel[x[i]]]+sum-res[top[bel[x[i]]]];
        }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<" \n"[i==m];
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

/*
1
6 7
13064 20716 6746 13064 6746 69225
5 5
4 1
4 1
1 6
4 5
3 2
3 2
*/

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 87700kb

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: 0
Accepted
time: 2833ms
memory: 155640kb

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...

output:

2 2 2 2 2 2 2
6 6 7 6 6 6 6 6
3 3 3 4 4 3 3
7 7 7 7
9 9 9 8 9 8 9 8 9 9 10 9 9
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
7 8
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
9 10 9
16 16 16 16 16 17 16 16
10 10 11 10 12 11 10 10 10 10 10 10 10 12 10 10 10 10 10 11
10 9 9 9 9 9 9 9 9 9 9 9 9 9 10 ...

result:

ok 5557 lines

Test #3:

score: 0
Accepted
time: 1508ms
memory: 146344kb

input:

10
100000 99999
3983 3983 20157 97983 20157 20157 3983 3983 97983 20157 20157 3983 97983 20157 3983 20157 20157 3983 3983 3983 97983 97983 20157 3983 3983 97983 20157 97983 20157 97983 3983 97983 97983 3983 20157 3983 20157 20157 97983 3983 3983 3983 3983 97983 97983 3983 97983 97983 3983 20157 3983...

output:

33392 33393 33393 33393 33393 33392 33392 33393 33393 33393 33392 33393 33393 33392 33393 33393 33392 33392 33392 33393 33393 33393 33392 33392 33393 33393 33393 33393 33393 33392 33393 33393 33392 33393 33392 33393 33393 33393 33392 33392 33392 33392 33393 33393 33392 33393 33393 33392 33393 33392 ...

result:

ok 10 lines

Test #4:

score: 0
Accepted
time: 1512ms
memory: 146396kb

input:

10
100000 99999
27534 27534 3780 3780 27534 53544 27534 3780 3780 53544 53544 27534 53544 53544 3780 3780 3780 3780 53544 27534 3780 3780 53544 27534 27534 53544 27534 27534 53544 27534 27534 27534 3780 27534 27534 3780 3780 3780 27534 53544 3780 53544 27534 3780 3780 3780 27534 27534 27534 3780 275...

output:

33613 33601 33601 33600 33600 33601 33601 33601 33600 33601 33600 33600 33601 33601 33601 33601 33601 33601 33600 33600 33601 33601 33601 33601 33600 33601 33601 33600 33601 33600 33601 33600 33601 33601 33601 33601 33600 33601 33601 33601 33601 33601 33601 33601 33601 33601 33600 33601 33600 33601 ...

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 1280ms
memory: 130420kb

input:

10
100000 99999
92499 92270 92270 92499 92499 92499 92270 54017 92270 92270 92270 54017 54017 54017 54017 92270 92499 54017 92270 54017 92499 92499 92270 92270 54017 54017 54017 54017 92270 92270 92499 54017 54017 92499 92499 54017 92270 92270 54017 92499 92270 92270 54017 54017 54017 92499 92499 54...

output:

33506 33482 33507 33482 33508 33483 33508 33483 33508 33483 33507 33483 33506 33483 33505 33483 33503 33483 33503 33482 33504 33483 33505 33483 33504 33483 33502 33483 33501 33483 33500 33482 33502 33483 33500 33483 33501 33482 33502 33483 33501 33483 33500 33482 33500 33483 33498 33483 33499 33483 ...

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 1309ms
memory: 132468kb

input:

10
100000 99999
76207 76207 88551 88551 98176 76207 98176 88551 88551 98176 88551 76207 76207 98176 98176 76207 76207 88551 76207 88551 76207 88551 88551 76207 88551 76207 98176 88551 76207 98176 88551 88551 76207 88551 98176 88551 76207 76207 98176 88551 76207 98176 76207 88551 88551 88551 88551 76...

output:

33484 33484 33476 33484 33477 33485 33476 33485 33477 33485 33477 33486 33477 33484 33477 33485 33476 33485 33476 33485 33476 33483 33477 33483 33477 33485 33476 33485 33477 33485 33476 33487 33476 33487 33476 33486 33477 33486 33476 33486 33477 33486 33476 33486 33476 33486 33477 33487 33477 33487 ...

result:

ok 10 lines

Test #7:

score: 0
Accepted
time: 1317ms
memory: 125496kb

input:

10
100000 99999
70486 49904 70486 49904 87935 49904 49904 87935 87935 49904 49904 87935 49904 87935 87935 70486 49904 87935 87935 49904 70486 87935 49904 70486 87935 87935 49904 49904 49904 87935 70486 70486 70486 49904 70486 87935 87935 87935 70486 87935 70486 49904 87935 49904 49904 87935 70486 87...

output:

33491 33486 33489 33486 33489 33486 33489 33486 33487 33486 33487 33486 33486 33485 33486 33486 33486 33486 33485 33486 33485 33485 33486 33486 33485 33486 33485 33486 33485 33485 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33486 33485 33485 33486 33485 ...

result:

ok 10 lines

Test #8:

score: 0
Accepted
time: 1263ms
memory: 129508kb

input:

10
100000 99999
98004 33580 98004 98004 98004 92291 92291 98004 98004 92291 92291 33580 98004 92291 33580 98004 98004 33580 98004 92291 92291 33580 92291 92291 98004 33580 98004 33580 33580 98004 33580 92291 33580 33580 92291 92291 92291 98004 33580 98004 92291 92291 33580 92291 98004 98004 92291 92...

output:

33462 33463 33421 33463 33422 33465 33421 33463 33422 33464 33422 33462 33422 33464 33421 33464 33422 33464 33422 33465 33422 33463 33422 33462 33422 33463 33422 33465 33421 33464 33422 33464 33422 33463 33422 33463 33421 33463 33421 33462 33422 33460 33422 33461 33421 33461 33422 33460 33422 33459 ...

result:

ok 10 lines