結果

問題 No.1212 Second Path
ユーザー penguinman
提出日時 2020-07-31 00:41:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 956 ms / 3,000 ms
コード長 5,425 bytes
コンパイル時間 2,741 ms
コンパイル使用メモリ 208,544 KB
実行使用メモリ 110,420 KB
最終ジャッジ日時 2024-10-15 03:25:46
合計ジャッジ時間 25,299 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define endl "\n"
using std::cin;
using std::cout;
using std::vector;
using ll=long long;
const ll inf=(1ll<<60);
struct tree{
int N;
vector<vector<int>> dp;
vector<int> dist;
tree(vector<vector<int>> edge){
N=edge.size();
dp.resize(N);
dist.resize(N,-1);
for(int i=0;i<N;i++) dp[i].resize(30);
dist[0]=dp[0][0]=0;
std::queue<int> que;
que.push(0);
while(!que.empty()){
int now=que.front(); que.pop();
for(int i=0;i<edge[now].size();i++){
int next=edge[now][i];
if(dist[next]==-1){
dist[next]=dist[now]+1;
que.push(next);
dp[next][0]=now;
}
}
}
for(int i=1;i<30;i++){
for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
}
}
std::tuple<int,int,int> LCA(int X,int Y){
if(dist[X]<dist[Y]) std::swap(X,Y);
int x=X;
{
int Z=dist[X]-dist[Y];
for(int i=0;i<30;i++){
if(Z&(1<<i)){
X=dp[X][i];
}
}
Z=dist[x]-dist[Y]-1;
for(int i=0;i<30;i++){
if(Z&(1<<i)){
x=dp[x][i];
}
}
}
if(X==Y){
return std::make_tuple(X,x,-1);
}
for(int i=29;i>=0;i--){
if(dp[X][i]!=dp[Y][i]){
X=dp[X][i];
Y=dp[Y][i];
}
}
return std::make_tuple(dp[X][0],X,Y);
}
};
struct Segment_tree{
int N;
vector<ll> node;
Segment_tree(int n):N(n){
{
int X=1;
while(X<N) X*=2;
N=X;
}
node.resize(2*N-1,inf);
}
ll compare(ll X,ll Y){
return std::min(X,Y);
}
void update(int X,ll Y){
X+=N-1;
node[X]=Y;
while(X){
X=(X-1)/2;
node[X]=compare(node[X*2+1],node[X*2+2]);
}
}
ll query(int a,int b,int now,int l,int r){
if(r<0) r=N;
if(r<=a||b<=l) return inf;
if(a<=l&&r<=b) return node[now];
return compare(query(a,b,now*2+1,l,(r+l)/2),query(a,b,now*2+2,(r+l)/2,r));
}
};
void dfs(int N,int now,vector<vector<int>> &edge,vector<vector<int>> &weight,tree &tr,Segment_tree &seg,vector<vector<std::tuple<int,int,int>>> &memo
    ,vector<ll> &min){
vector<ll> data;
std::map<int,int> cnt,match;
for(int i=0;i<edge[now].size();i++){
int next=edge[now][i];
if(tr.dist[next]>tr.dist[now]) data.push_back(weight[now][i]);
cnt[weight[now][i]]++;
match[next]=weight[now][i];
}
sort(data.begin(),data.end());
for(int i=0;i<edge[now].size();i++){
int next=edge[now][i];
if(tr.dist[next]>tr.dist[now]){
ll Z=data[0];
if(Z==weight[now][i]){
if(data.size()==1) Z=inf;
else Z=data[1];
}
seg.update(tr.dist[now],Z);
dfs(N,next,edge,weight,tr,seg,memo,min);
seg.update(tr.dist[now],inf);
}
}
for(auto p:memo[now]){
int X,Y,Z; std::tie(X,Y,Z)=p;
if(X>=0){
if(data.empty()) data.push_back(inf);
min[X]=std::min({min[X],seg.query(Y+1,Z,0,0,-1),data[0]});
}
else{
X=-X-1;
cnt[match[Y]]--;
if(cnt[match[Y]]==0) cnt.erase(match[Y]);
if(Z>=0){
cnt[match[Z]]--;
if(cnt[match[Z]]==0) cnt.erase(match[Z]);
}
if(!cnt.empty()) min[X]=std::min(min[X],(ll)(*begin(cnt)).first);
cnt[match[Y]]++;
if(Z>=0) cnt[match[Z]]++;
}
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
const ll MAX=1e5;
const ll INF=1e9;
int N; cin>>N;
assert(1<=N&&N<=MAX);
vector<vector<int>> edge(N),weight(N);
for(int i=1;i<N;i++){
int X,Y,Z; cin>>X>>Y>>Z;
assert(1<=X&&X<=N&&1<=Y&&Y<=N&&1<=Z&&Z<=INF);
edge[X-1].push_back(Y-1);
edge[Y-1].push_back(X-1);
weight[X-1].push_back(Z);
weight[Y-1].push_back(Z);
}
tree tr(edge);
int Q; cin>>Q;
assert(1<=Q&&Q<=MAX);
vector<vector<std::tuple<int,int,int>>> memo(N);
vector<ll> min(Q,inf),sum(Q),dist(N,-1);
dist[0]=0;
std::queue<int> que;
que.push(0);
while(!que.empty()){
int now=que.front(); que.pop();
for(int i=0;i<edge[now].size();i++){
int next=edge[now][i];
if(dist[next]==-1){
dist[next]=dist[now]+weight[now][i];
que.push(next);
}
}
}
for(int i=0;i<Q;i++){
int X,Y; cin>>X>>Y;
assert(1<=X&&X<=N&&1<=Y&&Y<=N&&X!=Y);
X--,Y--;
int Z,x,y;
std::tie(Z,x,y)=tr.LCA(X,Y);
if(X!=Z) memo[X].push_back(std::make_tuple(i,tr.dist[Z],tr.dist[X]));
if(Y!=Z) memo[Y].push_back(std::make_tuple(i,tr.dist[Z],tr.dist[Y]));
memo[Z].push_back(std::make_tuple(-i-1,x,y));
sum[i]=dist[X]+dist[Y]-2*dist[Z];
}
Segment_tree seg(N);
dfs(N,0,edge,weight,tr,seg,memo,min);
for(int i=0;i<Q;i++){
sum[i]+=min[i]*2;
if(min[i]==inf) sum[i]=-1;
cout<<sum[i]<<endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0