#include <vector>#include <algorithm>#include <iostream>#include <string>#include <cassert>usingnamespacestd;typedefvector<int>VI;#define PB push_back#define REP(i,n) for(int i=0; i<(n); ++i)#define ASF assert(false);structBipartiteDisjointSet{VIparent,rank,enemy,size;//parent : [1,n)BipartiteDisjointSet(intn):parent(n),rank(n,1),enemy(n,-1),size(n,1){REP(i,n)parent[i]=i;}intfind(intu){if(u==parent[u])returnu;returnparent[u]=find(parent[u]);}intmerge(intu,intv){if(u==-1orv==-1)returnmax(u,v);u=find(u);v=find(v);if(u==v)returnu;if(rank[u]>rank[v])swap(u,v);if(rank[u]==rank[v])++rank[v];parent[u]=v;size[v]+=size[u];returnv;}booldis(intu,intv){u=find(u);v=find(v);if(u==v)returnfalse;inta=merge(u,enemy[v]),b=merge(v,enemy[u]);enemy[a]=b;enemy[b]=a;returntrue;}boolack(intu,intv){u=find(u);v=find(v);if(enemy[u]==v)returnfalse;inta=merge(u,v),b=merge(enemy[u],enemy[v]);enemy[a]=b;if(b!=-1)enemy[b]=a;returntrue;}intmaxParty(){intret=0;REP(i,parent.size())if(this->find(i)==i){intenemy=this->enemy[i];if(enemy>i)continue;intmySize=this->size[i];intenemySize=(enemy==-1?0:this->size[enemy]);ret+=max(mySize,enemySize);}returnret;}};intN,M;intsolve(){cin>>N>>M;BipartiteDisjointSetA(N);REP(i,M){intu,v;stringstr;cin>>str>>u>>v;assert(str.size());if(str=="ACK"){if(notA.ack(u,v))return-(i+1);}elseif(str=="DIS"){if(notA.dis(u,v))return-(i+1);}/*else ASF*/}returnA.maxParty();}intmain(){intT;cin>>T;REP(i,T){intret=solve();if(ret<0)cout<<"CONTRADICTION AT "<<-ret<<endl;elsecout<<"MAX PARTY SIZE IS "<<ret<<endl;}return0;}
책과 같게 짜려고 했는데요, 입력을 받는 부분에서 문제가 있는 것 같습니다. 제출하면 RTE (SIGABRT: program aborted, probably assertion fail) 가 뜨는데요, assert 는 assert(str.size()) 에서만 사용되었습니다. character 배열로도 시도해보았지만 마찬가지 결과가 뜹니다. 어디서 실수한 것인지 잘 모르겠습니다ㅜㅜ 조언 부탁드립니다.
sven
EDITORWARS
책과 같게 짜려고 했는데요, 입력을 받는 부분에서 문제가 있는 것 같습니다. 제출하면 RTE (SIGABRT: program aborted, probably assertion fail) 가 뜨는데요, assert 는 assert(str.size()) 에서만 사용되었습니다. character 배열로도 시도해보았지만 마찬가지 결과가 뜹니다. 어디서 실수한 것인지 잘 모르겠습니다ㅜㅜ 조언 부탁드립니다.
10년 전