[Gym101194G][CHINA-Final2016]Pandaria

题目大意：
　　给你一个$n(n\le10^5)$个点，$m(m\le2\times10^5)$条边的无向图，每个点有一个颜色$c_i$，每条边有一个边权$w_i$。$q(q\le2\times10^5)$组询问$(x,w)$，每次询问从点$x$出发，只经过边权不超过$w$的边所能到达的连通块中，出现次数最多的颜色中，编号最小的颜色是多少？

思路：
　　Kruskal重构树+线段树合并。时间复杂度$O(m\log m+q\log n)$。

 #include<cstdio>

 #include<cctype>

 #include<climits>

 #include<cstring>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=2e5,logN=,M=2e5;

 int n,m,tot,ch[N][],val[N]={INT_MAX},ans[N];

 struct Edge {

     int u,v,w;

     bool operator < (const Edge &another) const {

         return w<another.w;

     }

 };

 Edge e[M];

 struct DisjointSet {

     int anc[N];

     void reset() {

         for(register int i=;i<N;i++) anc[i]=i;

     }

     int find(const int &x) {

         return x==anc[x]?x:anc[x]=find(anc[x]);

     }

     void merge(const int &x,const int &y) {

         anc[find(x)]=find(y);

     }

     bool same(const int &x,const int &y) {

         return find(x)==find(y);

     }

 };

 DisjointSet s;

 inline void kruskal() {

     tot=n;

     s.reset();

     std::sort(&e[],&e[m]);

     for(register int i=;i<m;i++) {

         const int &u=e[i].u,&v=e[i].v,&w=e[i].w;

         if(!s.same(u,v)) {

             val[++tot]=w;

             ch[tot][]=s.find(u);

             ch[tot][]=s.find(v);

             s.merge(u,tot);

             s.merge(v,tot);

         }

     }

 }

 class SegmentTree {

     private:

         struct Node {

             int max,val,left,right;

         };

         Node node[N/*logN];

         int new_node(const int &p) {

             node[++root[]]=node[p];

             return root[];

         }

         void push_up(const int &p) {

             if(node[node[p].left].max>=node[node[p].right].max) {

                 node[p].max=node[node[p].left].max;

                 node[p].val=node[node[p].left].val;

             } else {

                 node[p].max=node[node[p].right].max;

                 node[p].val=node[node[p].right].val;

             }

         }

     public:

         int root[N];

         void reset() {

             memset(root,,sizeof root);

         }

         void modify(int &p,const int &b,const int &e,const int &x) {

             p=new_node(p);

             if(b==e) {

                 node[p]=(Node){,x,,};

                 return;

             }

             const int mid=(b+e)>>;

             if(x<=mid) modify(node[p].left,b,mid,x);

             if(x>mid) modify(node[p].right,mid+,e,x);

             push_up(p);

         }

         int merge(const int &p,const int &q,const int &b,const int &e) {

             if(!p||!q) return p|q;

             if(b==e) {

                 node[p].max+=node[q].max;

                 return p;

             }

             const int mid=(b+e)>>;

             node[p].left=merge(node[p].left,node[q].left,b,mid);

             node[p].right=merge(node[p].right,node[q].right,mid+,e);

             push_up(p);

             return p;

         }

         int query(const int &p) const {

             return node[p].val;

         }

 };

 SegmentTree t;

 int dep[N],anc[N][logN];

 inline int log2(const float &x) {

     return ((unsigned&)x>>&)-;

 }

 void dfs(const int &x,const int &par) {

     dep[x]=dep[anc[x][]=par]+;

     for(register int i=;i<=log2(dep[x]);i++) {

         anc[x][i]=anc[anc[x][i-]][i-];

     }

     if(x<=n) return;

     dfs(ch[x][],x);

     dfs(ch[x][],x);

     t.root[x]=t.merge(t.root[ch[x][]],t.root[ch[x][]],,n);

     ans[x]=t.query(t.root[x]);

 }

 inline int find(int x,const int &w) {

     for(register int i=log2(dep[x]);~i;i--) {

         if(val[anc[x][i]]<=w) x=anc[x][i];

     }

     return x;

 }

 int main() {

     const int T=getint();

     for(register int i=;i<=T;i++) {

         t.reset();

         n=getint(),m=getint();

         for(register int i=;i<=n;i++) {

             t.modify(t.root[i],,n,ans[i]=val[i]=getint());

         }

         for(register int i=;i<m;i++) {

             const int u=getint(),v=getint(),w=getint();

             e[i]=(Edge){u,v,w};

         }

         kruskal();

         dfs(tot,);

         printf("Case #%d:\n",i);

         for(register int q=getint(),last=;q;q--) {

             const int x=getint()^last,w=getint()^last;

             printf("%d\n",last=ans[find(x,w)]);

         }

     }

     return ;

 }

巴特西

[Gym101194G][CHINA-Final2016]Pandaria

最新文章

热门文章