結果

問題 No.650 行列木クエリ
ユーザー HaarHaar
提出日時 2019-09-10 01:03:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,521 bytes
コンパイル時間 2,571 ms
コンパイル使用メモリ 206,452 KB
実行使用メモリ 818,048 KB
最終ジャッジ日時 2024-07-02 16:10:29
合計ジャッジ時間 6,223 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int d2(int)':
main.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
   40 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define L long long int
#define I int
#define R return
using namespace std;
const L m=1e9+7;
struct M{L a,b,c,d;};
M operator*(M x,M y){R{(x.a*y.a+x.b*y.c)%m,(x.a*y.b+x.b*y.d)%m,(x.c*y.a+x.d*y.c)%m,(x.c*y.b+x.d*y.d)%m};}
M u={1,0,0,1};
const I X=100010;
M S[X*2];
I s,z,n,q,o;
vector<vector<I>>T(X);
vector<I>B(X,1),P(X,-1),H(X),D(X);
pair<I,I>E[X];

M G(I x,I y,I i=0,I l=0,I r=s){
  if(r<=x||y<=l) R u;
  else if(x<=l&&r<=y) R S[i];
  R G(x,y,i*2+1,l,(l+r)/2)*G(x,y,i*2+2,(l+r)/2,r);
}

I d1(I C,I p){
  P[C]=p;
  I t=0;
  for(auto&N:T[C]){
    if(N==p)continue;
    B[C]+=d1(N,C);
    if(B[N]>t){t=B[N];swap(N,T[C][0]);}
  }
  R B[C];
}
I d2(I C){
  D[C]=o++;
  for(auto&N:T[C]){
    if(N==P[C])continue;
    H[N]=(N==T[C][0]?H[C]:N);
    d2(N);
  }
}

I main(){
  cin>>n;

  s=1;
  while(s<n)s*=2;
  z=s*2-1;
  while(z--)S[z+1]=u;
  
  for(I i=0;i<n-1;++i){
    I a,b;cin>>a>>b;
    T[a].push_back(b);
    T[b].push_back(a);
    E[i]={a,b};
  }

  cin>>q;
  d1(0,-1);d2(0);

  while(q--){
    char c;cin>>c;
    if(c-'g'){
      I i,x,y,z,w;cin>>i>>x>>y>>z>>w;
      auto[a,b]=E[i];
      I k=P[a]==b?D[a]:D[b],l=k+s-1;
      S[l--]={x,y,z,w};
      while(l>=0){S[l/2]=S[(l/2)*2+1]*S[(l/2)*2+2];(l/=2)--;}
    }else{
      I i,j;cin>>i>>j;
      M a=u;
      while(1){
        if(D[i]>D[j])swap(i,j);
        if(H[i]==H[j]){if(i!=j)a=G(D[i]+1,D[j]+1)*a;break;}
        a=G(D[H[j]],D[j]+1)*a;
        j=P[H[j]];
      }
      cout<<a.a<<" "<<a.b<<" "<<a.c<<" "<<a.d<<endl;
    }
  }

  R 0;
}
0