結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,440 KB
testcase_01 AC 21 ms
8,380 KB
testcase_02 AC 53 ms
12,920 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 20 ms
9,004 KB
testcase_05 AC 54 ms
12,920 KB
testcase_06 AC 3 ms
7,440 KB
testcase_07 AC 3 ms
8,364 KB
testcase_08 AC 458 ms
9,900 KB
testcase_09 TLE -
testcase_10 AC 3 ms
7,804 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:36:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:39:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:52:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
main.cpp:55:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |         scanf("%s", c);
      |         ~~~~~^~~~~~~~~
main.cpp:58:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |             scanf("%d%d%d%d%d", &j, &x00, &x01, &x10, &x11);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:66:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |             scanf("%d%d", &i, &j);
      |             ~~~~~^~~~~~~~~~~~~~~~

ソースコード

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