ABC264 E問題のバグの原因が不明です

C++

1#include <iostream>2#include <vector>3#include <queue>4#include <deque>5#include <map>6#include <set>7#include <cmath>8#include <cassert>9#include <algorithm>10#include <functional>11#include <stack>12#include <string>13#include <iomanip>14#include <tuple>15#include <numeric>16#include <algorithm>17#include <math.h>18// #include <atcoder/segtree>19// #include "atcoder/modint.hpp"20// using mint = atcoder::modint998244353;21using namespace std;22using ll = long long;23using dd = double;24// auto a1=make_pair(1,0);25// auto a2=make_pair(-1,0);26// auto a3=make_pair(0,1);27// auto a4=make_pair(0,-1);28// vector<pair<ll, ll> > V(0);29// V.push_back(a1);30// V.push_back(a2);31// V.push_back(a3);32// V.push_back(a4);33int ans=0;34int N,M,E,Q;35vector<bool> B(2000005, false);36vector<int> score(2000005, 0);37//o(logn)より高速ほぼ定数ちなみにby rankねこっちはサイズも求められるよただそれだけの違い038class DisjointSet{39 public:40 vector<int> rank, p, treesize;41 DisjointSet() {}42 DisjointSet(int size){43 rank.resize(size, 0);44 p.resize(size, 0);45 treesize.resize(size, 1);//根のみサイズとしては信用できます46 for(int i=0; i<size; i++) makeSet(i);47 }48 49 void makeSet(int x){50 p[x]=x;51 rank[x]=0;52 treesize[x]=1;53 }54 55 bool same(int x, int y){56 return findSet(x)==findSet(y);57 }58 59 void unite(int x,int y){60 link(findSet(x), findSet(y));61 }62 63 void link(int x, int y){64 if(x==y)return;65 int a,b;66 a=score[x];67 b=score[y];68 if(B[x]==true && B[y]==false){69 ans+=score[y];70 B[y]=true;71 score[x]+=b;72 score[y]+=a;73 }74 else if(B[y]==true && B[x]==false){75 ans+=score[x];76 B[x]=true;77 score[x]+=b;78 score[y]+=a;79 }80 else{81 score[x]+=b;82 score[y]+=a;83 }84 if(rank[x]>rank[y]){85 p[y]=x;86 }else{87 p[x]=y;88 if(rank[x]==rank[y]){89 rank[y]++;90 }91 }92 }93 94 int findSet(int x){95 if(x!=p[x]){96 p[x]=findSet(p[x]);97 }98 return p[x];99 }100};101int main(){102 103cin>>N>>M>>E;104for(int i=0;i<N;i++){105 score[i]=1;106}107for(int i=N;i<N+M;i++){108 B[i]=true;109}110DisjointSet U1(N+M);111vector<pair<int, int> > hen(E);112for(int i=0;i<E;i++){113 cin>>hen[i].first>>hen[i].second;114}115cin>>Q;116vector<int> saku(Q);117set<int> S;118for(int i=0;i<Q;i++){119 int p;120 cin>>p;121 p--;122 saku[i]=p;123 S.insert(saku[i]);124}125vector<int> A(0);126for(int i=0;i<E;i++){127 if(S.find(i)==S.end()){128 U1.unite(hen[i].first, hen[i].second);129 }130}131A.push_back(ans);132 133for(int i=saku.size()-1;i>=0;i--){134 U1.unite(hen[saku[i]].first,hen[saku[i]].second);135 A.push_back(ans);136}137 138for(int i=A.size()-2;i>=0;i--){139 cout<<A[i]<<endl;140}141}