結果

問題 No.416 旅行会社
ユーザー rickythetarickytheta
提出日時 2016-08-26 22:43:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,596 ms / 4,000 ms
コード長 4,514 bytes
コンパイル時間 1,573 ms
コンパイル使用メモリ 77,072 KB
実行使用メモリ 69,780 KB
最終ジャッジ日時 2023-08-21 09:36:38
合計ジャッジ時間 13,519 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 296 ms
64,016 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 3 ms
5,748 KB
testcase_08 AC 11 ms
4,548 KB
testcase_09 AC 55 ms
9,132 KB
testcase_10 AC 314 ms
63,760 KB
testcase_11 AC 362 ms
65,724 KB
testcase_12 AC 378 ms
54,548 KB
testcase_13 AC 318 ms
64,360 KB
testcase_14 AC 1,596 ms
69,780 KB
testcase_15 AC 1,154 ms
69,092 KB
testcase_16 AC 1,025 ms
68,968 KB
testcase_17 AC 1,181 ms
69,088 KB
testcase_18 AC 1,260 ms
68,692 KB
testcase_19 AC 833 ms
33,948 KB
testcase_20 AC 1,128 ms
34,000 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// AGC002
// http://agc002.contest.atcoder.jp/submissions/828130

// #include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <iostream>
 
using namespace std;
 
typedef pair<int,int> pii;
typedef int _loop_int;
#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)
 
// 永続配列
struct node{
  int lch,rch;
  int val,version;
};
node *nodes;
int nodehead;
void nodesinit(){
  nodehead = 0;
  nodes = (node*)calloc(8000000,sizeof(node));
}
int mynew(int val,int version){
  nodes[nodehead].val = val;
  nodes[nodehead].version = version;
  nodes[nodehead].lch = nodes[nodehead].rch = -1;
  return nodehead++;
}
#define SIZE 262144
#define VMAX 200002
#define DEFAULT -1
struct myarray{
  int now;
  int *rootid;
  myarray():now(0){
    rootid = (int*)calloc(VMAX,sizeof(int));
    rootid[0] = mynew(DEFAULT,0);
  }
  int getat(int v,int k){
    int l=0,r=SIZE;
    int curid = rootid[v];
    while(l+1<r){
      int c = (l+r)>>1;
      if(k<c){
        if(nodes[curid].lch==-1)return DEFAULT;
        r = c;
        curid = nodes[curid].lch;
      }else{
        if(nodes[curid].rch==-1)return DEFAULT;
        l = c;
        curid = nodes[curid].rch;
      }
    }
    return nodes[curid].val;
  }
  int setat_rec(int curid,int v,int k,int x,int l,int r,int id){
    if(l+1==r){
      if(nodes[curid].version == v){
        nodes[curid].val = x;
        return curid;
      }else{
        return mynew(x,v);
      }
    }else{
      int c = (l+r)>>1;
      if(k<c){
        int nxt=0;
        if(nodes[curid].lch==-1){
          int lch = mynew(DEFAULT,v);
          nxt = setat_rec(lch,v,k,x,l,c,(id<<1)+1);
        }else{
          nxt = setat_rec(nodes[curid].lch,v,k,x,l,c,(id<<1)+1);
        }
        if(nodes[curid].version == v){
          nodes[curid].lch = nxt;
          return curid;
        }else{
          int ret = mynew(DEFAULT,v);
          nodes[ret].rch = nodes[curid].rch;
          nodes[ret].lch = nxt;
          return ret;
        }
      }else{
        int nxt = 0;
        if(nodes[curid].rch==-1){
          int rch = mynew(DEFAULT,v);
          nxt = setat_rec(rch,v,k,x,c,r,(id<<1)+2);
        }else{
          nxt = setat_rec(nodes[curid].rch,v,k,x,c,r,(id<<1)+2);
        }
        if(nodes[curid].version == v){
          nodes[curid].rch = nxt;
          return curid;
        }else{
          int ret = mynew(DEFAULT,v);
          nodes[ret].lch = nodes[curid].lch;
          nodes[ret].rch = nxt;
          return ret;
        }
      }
    }
  }
  void setat(int v,int k,int x){
    rootid[v] = setat_rec(rootid[v],v,k,x,0,SIZE,0);
  }
  void record(){
    rootid[now+1] = mynew(DEFAULT,now+1);
    nodes[rootid[now+1]].lch = nodes[rootid[now]].lch;
    nodes[rootid[now+1]].rch = nodes[rootid[now]].rch;
    now += 1;
  }
};
 
int uf_root(myarray *uf,int v,int x){
  int r = uf->getat(v,x);
  if(r<0){
    return x;
  }else{
    return uf_root(uf,v,r);
  }
}
void uf_unite(myarray *uf,int v,int a,int b){
  a = uf_root(uf,v,a);
  b = uf_root(uf,v,b);
  if(a!=b){
    int sa = uf->getat(v,a);
    int sb = uf->getat(v,b);
    if(sa<=sb){
      uf->setat(v,a,sa+sb);
      uf->setat(v,b,a);
    }else{
      uf->setat(v,b,sa+sb);
      uf->setat(v,a,b);
    }
  }
}
int uf_same(myarray *uf,int v,int a,int b){
  return uf_root(uf,v,a)==uf_root(uf,v,b);
}
int uf_size(myarray *uf,int v,int a){
  return -uf->getat(v,uf_root(uf,v,a));
}
 
 
int n,m;
int q;

set<pii> ori;
vector<pii> del;
 
int main(){
  nodesinit();
  myarray *uf = new myarray();
 
  scanf("%d%d%d",&n,&m,&q);
  REP(i,m){
    int a,b;
    scanf("%d%d",&a,&b);
    --a;--b;
    ori.insert(pii(a,b));
  }
  REP(i,q){
    int a,b;
    scanf("%d%d",&a,&b);
    --a;--b;
    del.push_back(pii(a,b));
    ori.erase(ori.find(pii(a,b)));
  }
  for(pii P:ori){
    int a=P.first, b=P.second;
    uf_unite(uf,0,a,b);
  }
  uf->record();
  REP(i,q){
    pii P = del[q-1-i];
    int a=P.first, b=P.second;
    uf_unite(uf,i+1,a,b);
    uf->record();
  }

  FOR(i,1,n){
    int x=0, y=i;
    int low=-1,high=q+1;
    while(low+1<high){
      int mid = (low+high)>>1;
      int rx = uf_root(uf,mid,x);
      int ry = uf_root(uf,mid,y);
      if(rx!=ry){
        low = mid;
      }else{
        high = mid;
      }
    }
    printf("%d\n",low==-1 ? low : q-low);
  }
  return 0;
}
0