結果

問題 No.650 行列木クエリ
ユーザー latte0119latte0119
提出日時 2018-02-09 23:21:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 336 ms / 2,000 ms
コード長 3,567 bytes
コンパイル時間 2,011 ms
コンパイル使用メモリ 176,988 KB
実行使用メモリ 55,000 KB
最終ジャッジ日時 2024-04-17 15:04:04
合計ジャッジ時間 4,746 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
44,928 KB
testcase_01 AC 274 ms
46,976 KB
testcase_02 AC 336 ms
54,900 KB
testcase_03 AC 66 ms
44,800 KB
testcase_04 AC 258 ms
46,976 KB
testcase_05 AC 332 ms
55,000 KB
testcase_06 AC 65 ms
44,928 KB
testcase_07 AC 63 ms
44,800 KB
testcase_08 AC 182 ms
46,848 KB
testcase_09 AC 253 ms
54,412 KB
testcase_10 AC 66 ms
44,800 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0