Submission #19278231


Source Code Expand

Copy
#define _DEBUG
#include "bits/stdc++.h"
#include <atcoder/all>
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,a5,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#define debug_6(x1,x2,x3,x4,x5,x6) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<", "#x6<<": "<<x6<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_6,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define puba(a) emplace_back(a)
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace atcoder;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
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 (a>b) { a=b; return 1; } return 0; }
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
using Graph = vector<vpint>;

class lca {
public:
  int n;
  int log2_n;
  vector<vint> parent;//parent[k][v]:vから2^k回遡った親
  vector<int> depth;
  vector<vll> weight;//weight[k][v]:vから2^k回遡った親までの距離
  vector<vll> wmax;//wmax[k][v]:vから2^k回遡った親までの辺の重みの最大値

  lca() {}

  lca(const Graph &g, int root) // 辺が無向(双方向)の木であることを仮定
      : n(g.size()), log2_n(log2(n) + 2), parent(log2_n, vint(n)),
        depth(n,-1),weight(log2_n,vll(n)),wmax(log2_n,vll(n)) {
    if(!initialize(g,root)){
        cout << "LCA initialize error" << endl;
        assert(0);
    }
    for (int k = 0; k + 1 < log2_n; k++) {
      for (int v = 0; v < (int)g.size(); v++) {
        if (parent[k][v] < 0){
			parent[k + 1][v] = -1;
			weight[k + 1][v] = 0;
			wmax[k+1][v]=-1;
		}
        else{
			parent[k + 1][v] = parent[k][parent[k][v]];
			weight[k + 1][v] = weight[k][v] + weight[k][parent[k][v]];
			wmax[k + 1][v] = max(wmax[k][v],wmax[k][parent[k][v]]);
		}
      }
    }
  }

  bool initialize(const Graph &g,int v){
      dfs(g,v,-1,0,0);
      for(const auto& d:depth){
          if(d<=-1) return false;
      }
      int numberOfEdges=0;
      for(const auto& edges:g){
          numberOfEdges+=edges.size();
      }
      if(numberOfEdges!=2*((int)g.size()-1)) return false;
      return true;
  }

  void dfs(const Graph &g, int v, int p, int d,ll w) {
    parent[0][v] = p;
    depth[v] = d;
	weight[0][v]=w;
	wmax[0][v]=w;
    for (auto &e : g[v]) {
      if (e.first != p)
        dfs(g, e.first, v, d + 1, e.second);
    }
  }

  int get(int u, int v) {
    if (depth[u] > depth[v])
      swap(u, v);
    for (int k = 0; k < log2_n; k++) {
      if ((depth[v] - depth[u]) >> k & 1) {
        v = parent[k][v];
      }
    }
    if (u == v)
      return u;
    for (int k = log2_n - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
  ll getweight(int u, int v) {
	  ll sum=0;
	  if (depth[u] > depth[v])
		swap(u, v);
	  for (int k = 0; k < log2_n; k++) {
		if ((depth[v] - depth[u]) >> k & 1) {
		  sum+=weight[k][v];
		  v = parent[k][v];
		}
	  }
	  if (u == v)
		return sum;
	  for (int k = log2_n - 1; k >= 0; k--) {
		if (parent[k][u] != parent[k][v]) {
		  sum+=weight[k][u]+weight[k][v];
		  u = parent[k][u];
		  v = parent[k][v];
		}
	  }
	  return sum+weight[0][u]+weight[0][v];
  }
  ll getwmax(int u, int v) {
	ll ans=0;
	if (depth[u] > depth[v])
	  swap(u, v);
	for (int k = 0; k < log2_n; k++) {
	  if ((depth[v] - depth[u]) >> k & 1) {
		ans=max(ans,wmax[k][v]);
		v = parent[k][v];
	  }
	}
	if (u == v)
	  return ans;
	for (int k = log2_n - 1; k >= 0; k--) {
	  if (parent[k][u] != parent[k][v]) {
		ans=max({ans,wmax[k][u],wmax[k][v]});
		u = parent[k][u];
		v = parent[k][v];
	  }
	}
	return max({ans,weight[0][u],weight[0][v]});
  }
};
int main(){
	int N,M;
	scan(N>>M);
    dsu uf(N);
    int a[100001],b[100001];
    map<pint,bool> alre;
	rep(i,M){
        scan(a[i]>>b[i]);
        a[i]--; b[i]--;
        uf.merge(a[i],b[i]);
	}
    vector<vint> group=uf.groups();
    int belong[100001],indexingroup[100001];
    rep(i,group.size()){
        rep(j,group[i].size()){
            belong[group[i][j]]=i;
            indexingroup[group[i][j]]=j;
        }
    }
    Graph graphs[group.size()];
    rep(i,group.size()) graphs[i].resize(group[i].size());
    dsu uf2(N);
    rep(i,M){
        if(uf2.same(a[i],b[i])) continue;
        graphs[belong[a[i]]][indexingroup[a[i]]].puba(mp(indexingroup[b[i]],i));
        graphs[belong[a[i]]][indexingroup[b[i]]].puba(mp(indexingroup[a[i]],i));
        uf2.merge(a[i],b[i]);
    }
    vector<lca> lcas;
    rep(i,group.size()){
        lcas.emplace_back(graphs[i],0);
    }
	int Q;
	scan(Q);
	rep(q,Q){
		int x,y;
        scan(x>>y);
        x--; y--;
        if(uf.same(x,y)){
            prin(lcas[belong[x]].getwmax(indexingroup[x],indexingroup[y])+1);
        }
        else{
            prin(-1);
        }
	}
	return 0;
}

Submission Info

Submission Time
Task H - Union Sets
User gojira_ku
Language C++ (GCC 9.2.1)
Score 600
Code Size 6183 Byte
Status AC
Exec Time 361 ms
Memory 66776 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 8 ms 3748 KB
sample_02.txt AC 2 ms 3712 KB
sample_03.txt AC 2 ms 3656 KB
subtask_1_1.txt AC 2 ms 3592 KB
subtask_1_10.txt AC 32 ms 4064 KB
subtask_1_11.txt AC 144 ms 5216 KB
subtask_1_12.txt AC 66 ms 34488 KB
subtask_1_13.txt AC 6 ms 3668 KB
subtask_1_14.txt AC 4 ms 3588 KB
subtask_1_15.txt AC 64 ms 3984 KB
subtask_1_16.txt AC 12 ms 3752 KB
subtask_1_17.txt AC 28 ms 3724 KB
subtask_1_18.txt AC 3 ms 3728 KB
subtask_1_19.txt AC 57 ms 24924 KB
subtask_1_2.txt AC 2 ms 3536 KB
subtask_1_20.txt AC 2 ms 3816 KB
subtask_1_21.txt AC 18 ms 3672 KB
subtask_1_22.txt AC 37 ms 18992 KB
subtask_1_23.txt AC 285 ms 66596 KB
subtask_1_24.txt AC 281 ms 66708 KB
subtask_1_25.txt AC 283 ms 66300 KB
subtask_1_26.txt AC 289 ms 62856 KB
subtask_1_27.txt AC 357 ms 50752 KB
subtask_1_28.txt AC 361 ms 50888 KB
subtask_1_29.txt AC 289 ms 66596 KB
subtask_1_3.txt AC 5 ms 3796 KB
subtask_1_30.txt AC 288 ms 66600 KB
subtask_1_31.txt AC 283 ms 66304 KB
subtask_1_32.txt AC 290 ms 63016 KB
subtask_1_33.txt AC 342 ms 58032 KB
subtask_1_34.txt AC 348 ms 58028 KB
subtask_1_35.txt AC 286 ms 66656 KB
subtask_1_36.txt AC 284 ms 66776 KB
subtask_1_37.txt AC 286 ms 66384 KB
subtask_1_38.txt AC 283 ms 64500 KB
subtask_1_39.txt AC 298 ms 51096 KB
subtask_1_4.txt AC 85 ms 45332 KB
subtask_1_40.txt AC 291 ms 51316 KB
subtask_1_41.txt AC 163 ms 3476 KB
subtask_1_42.txt AC 172 ms 3596 KB
subtask_1_43.txt AC 279 ms 35028 KB
subtask_1_44.txt AC 327 ms 52140 KB
subtask_1_45.txt AC 162 ms 3580 KB
subtask_1_46.txt AC 283 ms 66576 KB
subtask_1_5.txt AC 29 ms 4200 KB
subtask_1_6.txt AC 65 ms 36036 KB
subtask_1_7.txt AC 12 ms 6972 KB
subtask_1_8.txt AC 26 ms 11272 KB
subtask_1_9.txt AC 44 ms 9516 KB