結果
問題 | 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 second typedef 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; }