結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2018-02-09 23:21:59 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 341 ms / 2,000 ms |
コード長 | 3,567 bytes |
コンパイル時間 | 3,261 ms |
コンパイル使用メモリ | 177,020 KB |
実行使用メモリ | 55,028 KB |
最終ジャッジ日時 | 2024-10-09 09:02:48 |
合計ジャッジ時間 | 5,594 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:132:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 132 | scanf("%lld",&N); | ~~~~~^~~~~~~~~~~ main.cpp:135:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 135 | scanf("%lld%lld",&a,&b); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:141:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 141 | int Q;scanf("%lld",&Q); | ~~~~~^~~~~~~~~~~ main.cpp:144:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 144 | scanf(" %c",&c); | ~~~~~^~~~~~~~~~ main.cpp:147:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 147 | scanf("%lld%lld",&x,&y); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:161:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 161 | int x;scanf("%lld",&x); | ~~~~~^~~~~~~~~~~ main.cpp:165:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 165 | rep(i,2)rep(j,2)scanf("%lld",&a[i][j]); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long long#define rep(i,n) for(int i=0;i<(n);i++)#define pb push_back#define all(v) (v).begin(),(v).end()#define fi first#define se secondtypedef vector<int>vint;typedef pair<int,int>pint;typedef vector<pint>vpint;template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}const int mod=1000000007;typedef vector<int>vec;typedef vector<vec>mat;mat I={{1,0},{0,1}};int mod_pow(int n,int m){int ret=1;while(m){if(m&1)ret=ret*n%mod;n=n*n%mod;m>>=1;}return ret;}mat mul(const mat &A,const mat &B){mat C(A.size(),vec(B[0].size()));for(int i=0;i<A.size();i++){for(int j=0;j<B[0].size();j++){for(int k=0;k<A[0].size();k++){C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;}}}return C;}mat mat_pow(mat A,int m){mat B(A.size(),vec(A.size()));for(int i=0;i<A.size();i++)B[i][i]=1;while(m){if(m&1)B=mul(B,A);A=mul(A,A);m>>=1;}return B;}struct segtree{static const int SEG=1<<17;vector<mat>dat;segtree():dat(SEG*2,I){}void update(int k,mat a){k+=SEG-1;dat[k]=a;while(k){k=(k-1)/2;dat[k]=mul(dat[k*2+1],dat[k*2+2]);}}mat query(int a,int b,int k=0,int l=0,int r=SEG){if(r<=a||b<=l)return I;if(a<=l&&r<=b)return dat[k];return mul(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));}};int N;vint G[111111];int A[111111],B[111111];const int SIZE=111111;int par[SIZE],dep[SIZE],hev[SIZE],pos[SIZE],head[SIZE],sz[SIZE];segtree seg;void dfs(){vint vs={0};par[0]=-1;dep[0]=0;rep(i,N){int v=vs[i];for(auto u:G[v]){if(u==par[v])continue;par[u]=v;dep[u]=dep[v]+1;vs.pb(u);}}for(int i=vs.size()-1;i>=0;i--){int v=vs[i];sz[v]=1;hev[v]=-1;int ma=0;for(auto u:G[v]){if(u==par[v])continue;if(ma<sz[u]){ma=sz[u];hev[v]=u;}sz[v]+=sz[u];}}}void init(){dfs();int idx=0;rep(i,N){if(~par[i]&&hev[par[i]]==i)continue;for(int j=i;~j;j=hev[j]){head[j]=i;pos[j]=idx++;}}/*ここでseg木を更新*/}signed main(){scanf("%lld",&N);rep(i,N-1){int a,b;scanf("%lld%lld",&a,&b);A[i]=a;B[i]=b;G[a].pb(b);G[b].pb(a);}init();int Q;scanf("%lld",&Q);while(Q--){char c;scanf(" %c",&c);if(c=='g'){int x,y;scanf("%lld%lld",&x,&y);mat a=I;while(head[x]!=head[y]){a=mul(seg.query(pos[head[y]],pos[y]+1),a);y=par[head[y]];}a=mul(seg.query(pos[x]+1,pos[y]+1),a);rep(i,2)rep(j,2){if(i||j)printf(" ");printf("%lld",a[i][j]);}puts("");}else{int x;scanf("%lld",&x);if(dep[A[x]]<dep[B[x]])swap(A[x],B[x]);x=A[x];mat a(2,vec(2));rep(i,2)rep(j,2)scanf("%lld",&a[i][j]);seg.update(pos[x],a);}}return 0;}