/ Vijos / 题库 / 战略游戏 /

题解

2 条题解

  • 1
    @ 2023-07-12 17:41:00 
    #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=100000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("5329.txt","r",stdin);
        freopen("5329.out","w",stdout);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int maxn=400002;
const int maxm=800002;
struct graph{
    int n,m;
    struct edge{
        int to,next;
    }e[maxm];
    int first[maxn];
    void addedge(int from,int to){
        e[++m]=(edge){to,first[from]};
        first[from]=m;
    }
};
struct block_cut_tree : graph{
    bool cir[maxn];
    int sz[maxn],fa[maxn],top[maxn],son[maxn],st[maxn],en[maxn],dist[maxn],dep[maxn],cl;
    void init(){
        memset(first,0,(n+1)*4);
        memset(cir,0,n+1);
        m=0;
    }
    void dfs(int u){
        st[u]=++cl;
        sz[u]=1;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (st[v])
                continue;
            dist[v]=dist[u]+cir[v];
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs(v);
            sz[u]+=sz[v];
            if (sz[v]>sz[son[u]])
                son[u]=v;
        }
        en[u]=cl;
    }
    void dfs2(int u,int tp){
        top[u]=tp;
        if (son[u])
            dfs2(son[u],tp);
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (!top[v])
                dfs2(v,v);
        }
    }
    void pre(){
        memset(son,0,(n+1)*4);
        memset(top,0,(n+1)*4);
        memset(st,0,(n+1)*4);
        cl=0;
        dist[1]=cir[1];
        dfs(1);
        dfs2(1,1);
    }
    int lca(int u,int v){
        for(;top[u]!=top[v];u=fa[top[u]])
            if (dep[top[u]]<dep[top[v]])
                swap(u,v);
        return dep[u]<dep[v]?u:v;
    }
    pair<int,int> b[maxn*2];
    int stk[maxn*2],tp;
    int work(int* a,int cnt){
        int sum=-cnt;
        for(int i=1;i<=cnt;i++)
            b[i]=make_pair(st[a[i]],a[i]);
        sort(b+1,b+cnt+1);
        for(int i=cnt-1;i;i--){
            int u=lca(b[i].second,b[i+1].second);
            b[++cnt]=make_pair(st[u],u);
        }
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        tp=0;
        for(int i=1;i<=cnt;i++){
            int u=b[i].second;
            while(tp && (st[u]<st[stk[tp]] || en[u]>en[stk[tp]]))
                tp--;
            if (tp)
                sum+=dist[u]-dist[stk[tp]];
            stk[++tp]=u;
        }
        if (cir[b[1].second])
            sum++;
        return sum;
    }
}t;
struct bcc_graph : graph{
    int low[maxn],dfn[maxn],cl,cnt;
    int stk[maxn],tp;
    void init(int n){
        this->n=n;
        memset(first,0,(n+1)*4);
        m=0;
    }
    void dfs(int u,int fa){
        low[u]=dfn[u]=++cl;
        stk[++tp]=u;
        bool qwq=0;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (v==fa && !qwq){
                qwq=1;
                continue;
            }
            if (dfn[v]){
                low[u]=min(low[u],dfn[v]);
                continue;
            }
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]){
                cnt++;
                t.addedge(u,cnt);
                for(;;){
                    int now=stk[tp--];
                    t.addedge(cnt,now);
                    if (now==v)
                        break;
                }
            }
        }
    }
    void build(){
        cnt=n;
        memset(low,0,(n+1)*4);
        memset(dfn,0,(n+1)*4);
        cl=tp=0;
        t.init();
        dfs(1,0);
        t.n=cnt;
        for(int i=1;i<=n;i++)
            t.cir[i]=1;
        t.pre();
    }
}g;
int a[maxn];
int main(){
    int size = 32 << 20;  // 32MB
    char *p = (char *)malloc(size) + size;
    __asm__ __volatile__("movq  %0, %%rsp\n" :: "r"(p));
    init();
    int T=readint();
    while(T--){
        int n=readint(),m=readint();
        g.init(n);
        while(m--){
            int u=readint(),v=readint();
            g.addedge(u,v);
            g.addedge(v,u);
        }
        g.build();
        int q=readint();
        while(q--){
            int k=readint();
            for(int i=1;i<=k;i++)
                a[i]=readint();
            printf("%d\n",t.work(a,k));
        }
    }
    exit(0);
}
  • 0
    @ 2018-06-03 21:29:47

    建出原图的圆方树（求点双时需要判下重边），对于每个询问，虚树上的圆点个数减去输入的点个数就是答案。
    注意Vijos的栈空间很小，所以需要手写栈或者黑科技（参见代码）。

    #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=100000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("5329.txt","r",stdin);
        freopen("5329.out","w",stdout);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int maxn=400002;
const int maxm=800002;
struct graph{
    int n,m;
    struct edge{
        int to,next;
    }e[maxm];
    int first[maxn];
    void addedge(int from,int to){
        e[++m]=(edge){to,first[from]};
        first[from]=m;
    }
};
struct block_cut_tree : graph{
    bool cir[maxn];
    int sz[maxn],fa[maxn],top[maxn],son[maxn],st[maxn],en[maxn],dist[maxn],dep[maxn],cl;
    void init(){
        memset(first,0,(n+1)*4);
        memset(cir,0,n+1);
        m=0;
    }
    void dfs(int u){
        st[u]=++cl;
        sz[u]=1;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (st[v])
                continue;
            dist[v]=dist[u]+cir[v];
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs(v);
            sz[u]+=sz[v];
            if (sz[v]>sz[son[u]])
                son[u]=v;
        }
        en[u]=cl;
    }
    void dfs2(int u,int tp){
        top[u]=tp;
        if (son[u])
            dfs2(son[u],tp);
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (!top[v])
                dfs2(v,v);
        }
    }
    void pre(){
        memset(son,0,(n+1)*4);
        memset(top,0,(n+1)*4);
        memset(st,0,(n+1)*4);
        cl=0;
        dist[1]=cir[1];
        dfs(1);
        dfs2(1,1);
    }
    int lca(int u,int v){
        for(;top[u]!=top[v];u=fa[top[u]])
            if (dep[top[u]]<dep[top[v]])
                swap(u,v);
        return dep[u]<dep[v]?u:v;
    }
    pair<int,int> b[maxn*2];
    int stk[maxn*2],tp;
    int work(int* a,int cnt){
        int sum=-cnt;
        for(int i=1;i<=cnt;i++)
            b[i]=make_pair(st[a[i]],a[i]);
        sort(b+1,b+cnt+1);
        for(int i=cnt-1;i;i--){
            int u=lca(b[i].second,b[i+1].second);
            b[++cnt]=make_pair(st[u],u);
        }
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        tp=0;
        for(int i=1;i<=cnt;i++){
            int u=b[i].second;
            while(tp && (st[u]<st[stk[tp]] || en[u]>en[stk[tp]]))
                tp--;
            if (tp)
                sum+=dist[u]-dist[stk[tp]];
            stk[++tp]=u;
        }
        if (cir[b[1].second])
            sum++;
        return sum;
    }
}t;
struct bcc_graph : graph{
    int low[maxn],dfn[maxn],cl,cnt;
    int stk[maxn],tp;
    void init(int n){
        this->n=n;
        memset(first,0,(n+1)*4);
        m=0;
    }
    void dfs(int u,int fa){
        low[u]=dfn[u]=++cl;
        stk[++tp]=u;
        bool qwq=0;
        for(int i=first[u];i;i=e[i].next){
            int v=e[i].to;
            if (v==fa && !qwq){
                qwq=1;
                continue;
            }
            if (dfn[v]){
                low[u]=min(low[u],dfn[v]);
                continue;
            }
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>=dfn[u]){
                cnt++;
                t.addedge(u,cnt);
                for(;;){
                    int now=stk[tp--];
                    t.addedge(cnt,now);
                    if (now==v)
                        break;
                }
            }
        }
    }
    void build(){
        cnt=n;
        memset(low,0,(n+1)*4);
        memset(dfn,0,(n+1)*4);
        cl=tp=0;
        t.init();
        dfs(1,0);
        t.n=cnt;
        for(int i=1;i<=n;i++)
            t.cir[i]=1;
        t.pre();
    }
}g;
int a[maxn];
int main(){
    int size = 32 << 20;  // 32MB
    char *p = (char *)malloc(size) + size;
    __asm__ __volatile__("movq  %0, %%rsp\n" :: "r"(p));
    init();
    int T=readint();
    while(T--){
        int n=readint(),m=readint();
        g.init(n);
        while(m--){
            int u=readint(),v=readint();
            g.addedge(u,v);
            g.addedge(v,u);
        }
        g.build();
        int q=readint();
        while(q--){
            int k=readint();
            for(int i=1;i<=k;i++)
                a[i]=readint();
            printf("%d\n",t.work(a,k));
        }
    }
    exit(0);
}
  • 1

战略游戏

信息

ID
2045
难度
6
分类
(无)
标签
递交数
55
已通过
19
通过率
35%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1