結果

問題 No.650 行列木クエリ
ユーザー はむこはむこ
提出日時 2017-04-09 09:57:32
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,821 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 44,648 KB
実行使用メモリ 17,444 KB
最終ジャッジ日時 2023-09-25 01:17:02
合計ジャッジ時間 4,064 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,592 KB
testcase_01 AC 21 ms
8,868 KB
testcase_02 AC 62 ms
12,872 KB
testcase_03 AC 3 ms
7,624 KB
testcase_04 AC 22 ms
8,868 KB
testcase_05 AC 61 ms
12,912 KB
testcase_06 AC 3 ms
7,600 KB
testcase_07 AC 3 ms
7,616 KB
testcase_08 AC 433 ms
9,768 KB
testcase_09 TLE -
testcase_10 AC 3 ms
7,584 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <cstdio>
#include <cstring>
#include <vector>

const int mod = (int)1e9+7;
const int MAX = 100000;

int n;
std::vector<int> g[MAX];
int es[MAX-1][2];
int par[MAX];
long long mat[MAX][4];
const long long id[4] = {1,0,0,1,};


void dfs(int v, int p) {
    par[v] = p;
    memcpy(mat[v], id, sizeof(id));
    for (int t : g[v]) if (t != p) dfs(t, v);
}

void merge(long long *a, long long *b) {
    long long t[] = {
        (a[0] * b[0] + a[1] * b[2]) % mod,
        (a[0] * b[1] + a[1] * b[3]) % mod,
        (a[2] * b[0] + a[3] * b[2]) % mod,
        (a[2] * b[1] + a[3] * b[3]) % mod,
    };
    memcpy(b, t, sizeof(t));
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        es[i][0] = a;
        es[i][1] = b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    for (int i = 0; i < n - 1; i++) {
        if (par[es[i][0]] == es[i][1]) {
            std::swap(es[i][0], es[i][1]);
        }
    }
    int q;
    scanf("%d", &q);
    while (q-- > 0) {
        char c[2];
        scanf("%s", c);
        if (c[0] == 'x') {
            int j, x00, x01, x10, x11;
            scanf("%d%d%d%d%d", &j, &x00, &x01, &x10, &x11);
            const int v = es[j][1];
            mat[v][0] = x00;
            mat[v][1] = x01;
            mat[v][2] = x10;
            mat[v][3] = x11;
        } else if (c[0] == 'g') {
            int i, j;
            scanf("%d%d", &i, &j);
            long long ans[4] = {1,0,0,1,};
            for (int v = j; v != i; v = par[v]) {
                merge(mat[v], ans);
            }
            printf("%d %d %d %d\n", (int)ans[0], (int)ans[1], (int)ans[2], (int)ans[3]);
        } else {
            throw;
        }
    }
}
0