| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 207156 | Segtree | Collapse (JOI18_collapse) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//ストレステスト
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
namespace solver1{
vi g[5010];
bool vis[5010];
void dfs(ll x){
if(vis[x])return ;
vis[x]=1;
for(auto y:g[x])dfs(y);
}
vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
int C=T.size(),Q=W.size();
for(int i=0;i<C;i++){
if(X[i]>Y[i])swap(X[i],Y[i]);
}
vi FANS(Q);
for(int i=0;i<Q;i++){
for(int j=0;j<N;j++){
g[j].clear();
vis[j]=0;
}
unordered_set<ll> S;
for(int j=0;j<=W[i];j++){
ll key=X[j]*5010+Y[j];
if(S.count(key))S.erase(key);
else S.insert(key);
}
for(auto key:S){
ll x=key/5010,y=key%5010;
if(not(x<=P[i]&&P[i]+1<=y)){
g[x].push_back(y);
g[y].push_back(x);
}
}
ll cnt=0;
for(int j=0;j<N;j++){
if(vis[j])continue;
dfs(j);
cnt++;
}
FANS[i]=cnt;
}
return FANS;
}
};
namespace solver2{
#define B 300
typedef struct qry{
ll p,id;
}qry;
vector<qry> Query[100010];
typedef struct edge{
ll t,x,y;
ll hash(){return x*100010+y;}
}edge;
edge Edge[100010];
vi FANS;
int component[100010];
vector<ll> g[100010];
bool vis[100010];
void dfs(ll x,ll co){
if(vis[x])return;
vis[x]=1;
if(co>=0)component[x]=co;
for(auto y:g[x])dfs(y,co);
}
vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){
rep(i,100010){
g[i].clear();
Query[i].clear();
}
int C=T.size(),Q=W.size();
for(int i=0;i<C;i++){
if(X[i]>Y[i])swap(X[i],Y[i]);
if(X[i]<=P[0]&&P[0]+1<=Y[i])X[i]=Y[i]=0;
Edge[i]=(edge){T[i],X[i],Y[i]};
}
for(int i=0;i<Q;i++){
Query[W[i]].push_back((qry){P[i],i});
}
FANS.resize(W.size());
for(int L=0;L<C;L+=B){
int R=min(L+B,C);
unordered_set<ll> BASE,S;
//BASE:クエリのバケット内でも常に存在する辺のハッシュの集合
//S:クエリのバケットのはじめに存在する、BASEに含まれない辺の集合
// 後にそれぞれのクエリを処理する時に変化させる
for(int i=0;i<L;i++){
ll has=Edge[i].hash();
if(BASE.count(has))BASE.erase(has);
else BASE.insert(has);
}
//BASEを求める
for(int i=L;i<R;i++){
ll has=Edge[i].hash();
if(BASE.count(has)){
BASE.erase(has);
S.insert(has);
}
}
//SをBASEを使って求める
for(int i=0;i<N;i++){g[i].clear();vis[i]=0;}
for(auto e:BASE){ll x=e/100010,y=e%100010;g[x].push_back(y);g[y].push_back(x);}
ll cc=0;
//cc:BASEのグラフの連結成分数
for(int i=0;i<N;i++){
if(vis[i])continue;
dfs(i,cc); cc++;
}
//BASEのグラフの連結成分を調べる
unordered_set<ll> conc;
//conc:クエリバケット内の辺の両端が属することのある連結成分の番号の集合
// このサイズは高々B個で、dfsで各クエリでの連結成分数を求めるのに使う
// それ以外のcc-conc個の成分は各クエリでも変わらず存在するので、加算すればok
for(int i=L;i<R;i++){
conc.insert(component[Edge[i].x]);
conc.insert(component[Edge[i].y]);
}
for(int i=L;i<R;i++){
ll has=Edge[i].hash();
if(S.count(has))S.erase(has);
else S.insert(has);
//この工事の後では、Sにハッシュ値を持つ辺の集合が存在する
for(auto t:conc){
vis[t]=0;
g[t].clear();
}
for(auto e:S){
ll x=e/100010,y=e%100010;
x=component[x],y=component[y];
if(x!=y){
g[x].push_back(y);
g[y].push_back(x);
}
}
ll cnt=0;
for(auto t:conc){
if(vis[t])continue;
dfs(t,-1);
cnt++;
}
//concの頂点とSの辺のグラフの連結成分数cntを調べる
//cerr<<__LINE__<<cc<<" "<<conc.size()<<" "<<cnt<<endl;
for(qry q:Query[i]){
FANS[q.id]=cc-conc.size()+cnt;
}
//i番目の工事が終わったあとの連結成分数を答える
}
}
return FANS;
}
};
int main(){
string typ="rand";
while(1){
ll N,C,Q;
if(typ=="hand")cin>>N>>C>>Q;
if(typ=="rand")N=500,C=500,Q=500;
vi T(C),X(C),Y(C),W(Q),P(Q);
rep(i,C){
if(typ=="hand")cin>>T[i]>>X[i]>>Y[i];
if(typ=="rand"){
bool done=0;
if(rand()%5==0&&i>=1){
ll id=rand()%i;
if(T[id]==0){
T[i]=1;
X[i]=X[id],Y[i]=Y[id];
done=1;
}
}
if(done==0){
T[i]=0;
X[i]=rand()%N;
Y[i]=rand()%N;
}
}
}
rep(i,Q){
if(typ=="hand")cin>>W[i]>>P[i];
if(typ=="rand"){
W[i]=rand()%C;
P[i]=-10;
}
}
sort(W.begin(),W.end());
vi ANS1=solver1::simulateCollapse(N,T,X,Y,W,P);
vi ANS2=solver2::simulateCollapse(N,T,X,Y,W,P);
if(ANS1==ANS2)cout<<"Accepted"<<endl;
else cout<<"WrongAnswer"<<endl;
for(int i=0;i<Q;i++){
if(ANS1[i]!=ANS2[i]){
cout<<W[i]<<" "<<ANS1[i]<<" "<<ANS2[i]<<endl;
}
}
getchar();
}
}