結果

問題 No.650 行列木クエリ
ユーザー latte0119latte0119
提出日時 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]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

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

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0