Submission #18941267


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
template<typename T>
using prque = priority_queue<T,vector<T>>;
template<typename T>
using prquer = priority_queue<T,vector<T>,greater<T>>;
#define umap unordered_map
#define uset unordered_set
#define umset unordered_multiset

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EB emplace_back
#define EF emplace_front
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define MP make_pair
#define MT make_tuple
#define SZ(a) (int)((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define SORTR(c) sort((c).rbegin(), (c).rend())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB lower_bound
#define UB upper_bound
#define NEXP(a) next_permutation((a).begin(),(a).end())
#define FI first
#define SE second

#define FOR(i,a,b) for(auto i = decltype(b){a}; i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define FORR(i,a,b) for(auto i=decltype(b){b-1}; i>=(a); i--)
#define REPR(i,n) FORR(i,0,n)
#define CFOR(i,a,b) for(auto i = decltype(b){a}; i<=(b); i++)
#define CREP(i,n) CFOR(i,0,n)
#define SREP(i,n) CFOR(i,1,n)
#define CFORR(i,a,b) for(auto i=decltype(b){b}; i>=(a); i--)
#define CREPR(i,n) CFORR(i,0,n)
#define SREPR(i,n) CFORR(i,1,n)
#define BFOR(bit,a,b) for(LL bit=(a); bit<(1ll<<(b)); bit++)
#define BREP(bit,n) BFOR(bit,0,n)
#define EACH(ptr,c) for(auto ptr=(c).begin(); ptr!=(c).end(); )
#define EACHR(ptr,c) for(auto ptr=(c).rbegin(); ptr!=(c).rend(); )

constexpr double EPS = 1e-10;
constexpr double PI  = 3.141592653589793238462643383279;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr LL LINF = numeric_limits<LL>::max()/3;
constexpr int RINF = numeric_limits<int>::min()/2;
constexpr LL RLINF = numeric_limits<LL>::min()/3;
constexpr LL MOD = 1e9+7;
constexpr LL MODD = 998244353;
constexpr int MAX = 510000;

template<class T> inline T sqr(T x) { return x*x; }
inline bool Eq(double a, double b) { return fabs(b - a) < EPS; }
template<class T> inline T CEIL(T x, T y) { return (x+y-1)/y; }
inline int PCnt(uint64_t x) { return __builtin_popcountll(x); }

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline LL toLL(string s) {LL v; istringstream sin(s);sin>>v;return v;}
inline double toDouble(string s) {double v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toStr(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename T>
T Vsum(vector<T> &v){return reduce(v.begin(),v.end()); }
template<typename T>
T Vgcd(vector<T> &v){return reduce(v.begin(),v.end(),T(0),[](auto&&a,auto&&b){return gcd(a,b);}); }
template<typename T>
T Vlcm(vector<T> &v){return reduce(v.begin(),v.end(),T(1),[](auto&&a,auto&&b){return lcm(a,b);}); }

template<typename T> T Vmax(vector<T> &v){return *max_element(v.begin(),v.end()); }
template<typename T> T Vmin(vector<T> &v){return *min_element(v.begin(),v.end()); }
template<typename T> void Vadd(vector<T> &v, T a){for(auto&& x : v) x += a; }

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...)); }

const vector<int> dx = {1,0,-1,0,1,1,-1,-1};
const vector<int> dy = {0,1,0,-1,1,-1,1,-1};

#define debug(x) cerr << #x <<" : "<< x << endl;
bool cYN(bool fl=true){cout << (fl?"Yes":"No") << endl; return fl; }
bool CYN(bool fl=true){cout << (fl?"YES":"NO") << endl; return fl; }
void error(bool fl=true){cout << -1 << endl; if(fl){ exit(0);} }
template<class T> void COUT(T&& t){ cout << t << endl; }
template<class T,class... Ts>
void COUT(T&& t,Ts&&... ts){ cout << t << " "; COUT(forward<Ts>(ts)...); }

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second; return is;
}
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << p.first << " " << p.second; return os;
}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < SZ(v); i++) os << v[i] << (i + 1 != SZ(v) ? " " : "");
  return os;
}

struct UnionFind {
  
  VI par, siz;
  int cnt,n,smax;
  
  UnionFind() {}
  
  UnionFind(int n_):par(n_), siz(n_,1),cnt(n_),n(n_),smax(1) {
    iota(ALL(par),0);
  }
  
  void init(int n_) {
    par.assign(n_,0);
    siz.assign(n_,1);
    iota(ALL(par),0);
    cnt = n_;
    n = n_;
    smax = 1;
  }
  
  int find(int x) {
    if(par[x] == x){
      return x;
    }else{
      return par[x] = find(par[x]);
    }
  }

  bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    cnt--;

    if(siz[x] < siz[y]){
      swap(x,y);
    }
    siz[x] += siz[y];
    chmax(smax, siz[x]);
    par[y] = x;
    return true;
  }

  bool same(int x, int y){
    return find(x) == find(y);
  }
  
  int size(int x){
    return siz[find(x)];
  }


  VVI groups() {
    VI leader_buf(n), group_size(n);
    REP(i,n){
      leader_buf.at(i) = find(i);
      group_size.at(leader_buf.at(i))++;
    }
    VVI result(n);
    REP(i,n){
      result.at(i).reserve(group_size.at(i));
    }
    REP(i,n){
      result.at(leader_buf.at(i)).EB(i);
    }
    result.erase(
      remove_if(
        ALL(result),
        [&](const VI& v) { return v.empty(); }
      ),
      result.end()
    );
    return result;
  }

};

int main() {

  // cin.tie(0);
  // ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  
  int N, M;
  cin >> N >> M;
  VI a(M), b(M);
  REP(i,M){
    cin >> a.at(i) >> b.at(i);
    a.at(i)--; b.at(i)--;
  }
  int Q;
  cin >> Q;
  VI x(Q), y(Q);
  REP(i,Q){
    cin >> x.at(i) >> y.at(i);
    x.at(i)--; y.at(i)--;
  }

  VI ok(Q, M+1), ng(Q, -1);
  VVI wj(M+1);

  auto con = [&](){
    bool res = false;
    wj.assign(M+1,VI(0));
    REP(i,Q)if(abs(ok.at(i)-ng.at(i))>1){
      res = true;
      int mid = (ok.at(i)+ng.at(i))/2;
      wj.at(mid).PB(i);
    }
    return res;
  };

  while(con()){
    UnionFind uf(N);
    CREP(i,M){
      for(auto&&p : wj.at(i)){
        (uf.same(x.at(p), y.at(p))?ok.at(p):ng.at(p)) = i;
      }
      if(i!=M) uf.unite(a.at(i), b.at(i));
    }
  }

  VI ans(Q);
  REP(i,Q) ans.at(i) = ((ok.at(i)==M+1)?-1:ok.at(i));

  for(auto&&x : ans){
    COUT(x);
  }

  return 0;
}
/*
制約は見ましたか?
実行時間制限は見ましたか?
サンプルは試しましたか?
cat in.txt | .\a.exe > out.txt
C++になっていますか?
//*/

Submission Info

Submission Time
Task H - Union Sets
User Suu0313
Language C++ (GCC 9.2.1)
Score 600
Code Size 7516 Byte
Status AC
Exec Time 320 ms
Memory 18780 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 9 ms 3536 KB
sample_02.txt AC 2 ms 3568 KB
sample_03.txt AC 2 ms 3480 KB
subtask_1_1.txt AC 2 ms 3512 KB
subtask_1_10.txt AC 40 ms 5008 KB
subtask_1_11.txt AC 171 ms 11584 KB
subtask_1_12.txt AC 10 ms 3616 KB
subtask_1_13.txt AC 9 ms 3468 KB
subtask_1_14.txt AC 9 ms 3540 KB
subtask_1_15.txt AC 66 ms 5516 KB
subtask_1_16.txt AC 9 ms 3784 KB
subtask_1_17.txt AC 22 ms 3844 KB
subtask_1_18.txt AC 4 ms 3492 KB
subtask_1_19.txt AC 15 ms 3740 KB
subtask_1_2.txt AC 2 ms 3488 KB
subtask_1_20.txt AC 6 ms 3540 KB
subtask_1_21.txt AC 17 ms 3768 KB
subtask_1_22.txt AC 5 ms 3720 KB
subtask_1_23.txt AC 189 ms 6972 KB
subtask_1_24.txt AC 191 ms 8144 KB
subtask_1_25.txt AC 193 ms 9204 KB
subtask_1_26.txt AC 212 ms 11128 KB
subtask_1_27.txt AC 319 ms 15956 KB
subtask_1_28.txt AC 313 ms 16052 KB
subtask_1_29.txt AC 186 ms 6968 KB
subtask_1_3.txt AC 4 ms 3536 KB
subtask_1_30.txt AC 193 ms 8220 KB
subtask_1_31.txt AC 198 ms 9244 KB
subtask_1_32.txt AC 210 ms 11060 KB
subtask_1_33.txt AC 310 ms 15676 KB
subtask_1_34.txt AC 315 ms 15720 KB
subtask_1_35.txt AC 187 ms 6880 KB
subtask_1_36.txt AC 196 ms 8124 KB
subtask_1_37.txt AC 192 ms 9324 KB
subtask_1_38.txt AC 208 ms 11252 KB
subtask_1_39.txt AC 314 ms 18728 KB
subtask_1_4.txt AC 19 ms 3968 KB
subtask_1_40.txt AC 320 ms 18780 KB
subtask_1_41.txt AC 166 ms 5908 KB
subtask_1_42.txt AC 172 ms 7256 KB
subtask_1_43.txt AC 265 ms 14244 KB
subtask_1_44.txt AC 300 ms 15456 KB
subtask_1_45.txt AC 164 ms 5744 KB
subtask_1_46.txt AC 181 ms 5972 KB
subtask_1_5.txt AC 42 ms 5140 KB
subtask_1_6.txt AC 6 ms 3696 KB
subtask_1_7.txt AC 2 ms 3524 KB
subtask_1_8.txt AC 2 ms 3572 KB
subtask_1_9.txt AC 42 ms 3932 KB