結果

問題 No.1600 Many Shortest Path Problems
コンテスト
ユーザー limbo
提出日時 2025-12-13 20:23:11
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 368 ms / 4,000 ms
コード長 4,057 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,956 ms
コンパイル使用メモリ 211,896 KB
実行使用メモリ 73,996 KB
最終ジャッジ日時 2025-12-13 20:23:30
合計ジャッジ時間 16,987 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll = long long; 

const ll MOD=1e9+7;
const ll LOGN=20;
const ll MAXN=200005;

struct edge{
	ll u,v, og_id;
	ll c;
	ll w_mod;
	bool in_mst;
};

vector<edge> edges;
vector<pair<ll,ll>> mst_adj[MAXN];

ll up[MAXN][LOGN];
ll depth[MAXN];
ll tin[MAXN],tout[MAXN],timer;
ll dist_from_root[MAXN];
ll edge_index_up[MAXN];

vector<ll> best_replacement;
vector<ll> original_to_sorted_idx;

ll power(ll base, ll exp){
	ll ans=1;
	while(exp>0){
		if(exp%2==1){
			ans=(ans*base)%MOD;
		}
		base=(base*base)%MOD;
		exp/=2;
	}
	return ans;
}

struct DSU{
	vector<ll> parent;
	DSU(ll n){
		parent.resize(n+1);
		iota(parent.begin(),parent.end(),0);
	}
	ll find(ll i){
		if(parent[i]==i){
			return i;
		}
		return parent[i]=find(parent[i]);
	}
	void unite(ll i, ll j){
		ll root_i=find(i); 
		ll root_j=find(j);
		if(root_i!=root_j){
			parent[root_i]=root_j;
		}
	}
};

void dfs(ll u, ll p, ll edge_idx, ll current_dist){
	tin[u]=timer; timer++;
	
	if(u==p){depth[u]=0;}else{depth[u]=depth[p]+1;}

	up[u][0]=p;
	dist_from_root[u]=current_dist;
	edge_index_up[u]=edge_idx;

	for(ll i=1; i<LOGN; i++){
		up[u][i]=up[up[u][i-1]][i-1];
	}

	for(auto e:mst_adj[u]){
		ll v=e.first;
		ll idx=e.second;
		if(v!=p){
			dfs(v,u,idx,(current_dist+edges[idx].w_mod)%MOD);
		}
	}
	tout[u]=timer; timer++;
}

bool is_ancestor(ll u, ll v){
	return tin[u]<=tin[v] && tout[u]>=tout[v];
}

ll get_lca(ll u, ll v){
	if(is_ancestor(u,v)){return u;}
	if(is_ancestor(v,u)){return v;}
	for(ll i=LOGN-1; i>=0; i--){
		if(!is_ancestor(up[u][i],v)){u=up[u][i];}
	}
	return up[u][0];
}

ll path_cost(ll u, ll v){
	ll lca=get_lca(u, v);
	ll ans=(dist_from_root[u]+dist_from_root[v])%MOD;
	ll ext=(2*dist_from_root[lca])%MOD;
	return (ans-ext+MOD)%MOD;
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n,m,q;
    cin>>n>>m;
    for(ll i=1; i<=m; i++){
    	ll u,v,c=i;
    	cin>>u>>v;
    	edge e;
    	e.u=u;
    	e.v=v;
    	e.c=c;
    	e.w_mod=power(2,c);
    	e.og_id=i;
    	e.in_mst=0;
    	edges.push_back(e);
    }

    sort(edges.begin(),edges.end(),[](const edge& a, const edge& b){
    	return a.c<b.c;
    });

    original_to_sorted_idx.resize(m+1);

    for(ll i=0; i<m; i++){
    	original_to_sorted_idx[edges[i].og_id]=i;
    }

    DSU dsu_mst(n);

    for(ll i=0; i<m; i++){
    	if(dsu_mst.find(edges[i].u)!=dsu_mst.find(edges[i].v)){
    		dsu_mst.unite(edges[i].u,edges[i].v);
    		edges[i].in_mst=1;
    		mst_adj[edges[i].u].push_back({edges[i].v,i});
    		mst_adj[edges[i].v].push_back({edges[i].u,i});
    	}
    }

    timer=0;
    dfs(1,1,-1,0);

    best_replacement.assign(m+1,-1);
    DSU dsu2(n);

    for(ll i=0; i<m;i++){
    	if(!edges[i].in_mst){
    		ll u=edges[i].u;
    		ll v=edges[i].v;
    		ll lca=get_lca(u,v);

    		auto fun=[&](ll cur){
    			cur=dsu2.find(cur);

    			while(depth[cur]>depth[lca]){

    				if(best_replacement[edge_index_up[cur]]==-1){
    					best_replacement[edge_index_up[cur]]=i;
    				}

    				dsu2.unite(cur,up[cur][0]);
    				cur=dsu2.find(cur);
    			}

    		};

    		fun(u);
    		fun(v);
    	}
    }
    cin>>q;
    while(q--){
    	ll x,y,z;
    	cin>>x>>y>>z;

    	ll k=original_to_sorted_idx[z];
    	edge& rem_edge=edges[k];
    	ll base_dist=path_cost(x,y);

    	if(!rem_edge.in_mst){
    		cout<<base_dist<<'\n';
    		continue;
    	}

    	ll u=rem_edge.u;
    	ll v=rem_edge.v;
    	if(depth[u]>depth[v]){swap(u,v);}

    	bool x_in_v=is_ancestor(v,x);
    	bool y_in_v=is_ancestor(v,y);
    	if(x_in_v==y_in_v){
    		cout<<base_dist<<'\n'; continue;
    	}
    	
    	ll rep_sort_idx=best_replacement[k];
    	if(rep_sort_idx==-1){cout<<"-1"<<'\n'; continue;}

    	edge& rep_edge=edges[rep_sort_idx];
    	ll rx=rep_edge.u;
    	ll ry=rep_edge.v;

    	ll s1,s2;
    	if(is_ancestor(v,rx)==x_in_v){
    		s1=path_cost(x,rx);
    		s2=path_cost(y,ry);
    	}
    	else{
    		s1=path_cost(x,ry);
    		s2=path_cost(y,rx);
    	}

    	ll ans=(s1+s2+rep_edge.w_mod)%MOD;
    	cout<<ans<<'\n';
    }

    return 0;
}
0