結果
| 問題 |
No.650 行列木クエリ
|
| コンテスト | |
| ユーザー |
 tnakao0123
|
| 提出日時 | 2018-02-17 16:56:02 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,978 bytes |
| コンパイル時間 | 1,368 ms |
| コンパイル使用メモリ | 100,124 KB |
| 実行使用メモリ | 20,964 KB |
| 最終ジャッジ日時 | 2024-06-24 12:14:33 |
| 合計ジャッジ時間 | 2,972 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 3 WA * 7 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:115:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
115 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
main.cpp:119:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
119 | scanf("%d%d", &ai, &bi);
| ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:201:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
201 | scanf("%d", &qn);
| ~~~~~^~~~~~~~~~~
main.cpp:205:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
205 | scanf("%s", op);
| ~~~~~^~~~~~~~~~
main.cpp:210:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
210 | scanf("%d%lld%lld%lld%lld", &i, &x00, &x01, &x10, &x11);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:218:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
218 | scanf("%d%d", &i, &j);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-
*
* 650.cc: No.650 行列木クエリ - yukicoder
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
/* constant */
const int MAX_N = 100000;
const int MAX_K = 18;
const int MAX_E2 = 1 << 18;
const long long MOD = 1000000007;
/* typedef */
typedef long long ll;
typedef queue<int> qi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
struct Mat {
ll x00, x01, x10, x11;
Mat(): x00(1), x01(0), x10(0), x11(1) {}
Mat(ll _x00, ll _x01, ll _x10, ll _x11):
x00(_x00), x01(_x01), x10(_x10), x11(_x11) {}
void unit() { x00 = x11 = 1, x01 = x10 = 0; }
void set(ll _x00, ll _x01, ll _x10, ll _x11) {
x00 = _x00, x01 = _x01, x10 = _x10, x11 = _x11;
}
Mat operator*(const Mat &m) const {
return Mat((x00 * m.x00 + x01 * m.x10) % MOD,
(x00 * m.x01 + x01 * m.x11) % MOD,
(x10 * m.x00 + x11 * m.x10) % MOD,
(x10 * m.x01 + x11 * m.x11) % MOD);
}
void print() { printf("%lld %lld %lld %lld\n", x00, x01, x10, x11); }
};
template <typename T, const int MAX_E2>
struct SegTreeMul {
int n, e2;
T nodes[MAX_E2], one;
SegTreeMul() {}
void init(int _n, T _one) {
n = _n;
one = _one;
for (e2 = 1; e2 < n; e2 <<= 1);
fill(nodes, nodes + MAX_E2, one);
}
T get(int i) { return nodes[e2 - 1 + i]; }
void set(int i, T v) {
int j = e2 - 1 + i;
nodes[j] = v;
j = (j - 1) / 2;
for (;;) {
nodes[j] = nodes[j * 2 + 1] * nodes[j * 2 + 2];
if (j == 0) break;
j = (j - 1) / 2;
}
}
T mul_range(int r0, int r1, int k, int i0, int i1) {
if (r1 <= i0 || i1 <= r0) return one;
if (r0 <= i0 && i1 <= r1) return nodes[k];
int im = (i0 + i1) / 2;
T v0 = mul_range(r0, r1, k * 2 + 1, i0, im);
T v1 = mul_range(r0, r1, k * 2 + 2, im, i1);
return v0 * v1;
}
T mul_range(int r0, int r1) { return mul_range(r0, r1, 0, 0, e2); }
};
/* global variables */
vpii nbrs[MAX_N];
SegTreeMul<Mat,MAX_E2> st;
int prts[MAX_N], peis[MAX_N], cns[MAX_N], szs[MAX_N];
int sids[MAX_N], gtvs[MAX_N], gtes[MAX_N];
/* subroutines */
/* main */
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
int ai, bi;
scanf("%d%d", &ai, &bi);
nbrs[ai].push_back(pii(bi, i));
nbrs[bi].push_back(pii(ai, i));
}
prts[0] = peis[0] = -1;
qi q;
q.push(0);
while (! q.empty()) {
int u = q.front(); q.pop();
int &up = prts[u];
vpii &nbru = nbrs[u];
for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
int &v = vit->first, &ve = vit->second;
if (v != up) {
cns[u]++;
prts[v] = u;
peis[v] = ve;
q.push(v);
}
}
}
//for (int i = 0; i < n; i++) printf("%d ", cns[i]); putchar('\n');
for (int i = 0; i < n; i++) {
szs[i] = 1;
if (cns[i] == 0) q.push(i);
}
while (! q.empty()) {
int u = q.front(); q.pop();
int &up = prts[u];
if (up >= 0) {
szs[up] += szs[u];
if (--cns[up] == 0) q.push(up);
}
}
//for (int i = 0; i < n; i++) printf("%d ", szs[i]); putchar('\n');
for (vpii::iterator vit = nbrs[0].begin(); vit != nbrs[0].end(); vit++)
q.push(vit->first);
int sn = 0;
while (! q.empty()) {
int u = q.front(); q.pop();
int &up = prts[u], &uei = peis[u];
sids[uei] = sn++;
gtvs[u] = up;
gtes[u] = uei;
for (int cu = u; cu >= 0;) {
int &cup = prts[cu];
vpii &nbrcu = nbrs[cu];
int maxsz = 0, maxi = -1;
for (vpii::iterator vit = nbrcu.begin(); vit != nbrcu.end(); vit++) {
int &v = vit->first;
if (v != cup && maxsz < szs[v]) maxsz = szs[v], maxi = v;
}
if (maxi < 0) break;
for (vpii::iterator vit = nbrcu.begin(); vit != nbrcu.end(); vit++) {
int &v = vit->first;
if (v != cup) {
if (v != maxi) q.push(v);
else {
int &vei = peis[v];
sids[vei] = sn++;
gtvs[v] = up;
gtes[v] = uei;
}
}
}
cu = maxi;
}
}
st.init(n - 1, Mat());
int qn;
scanf("%d", &qn);
while (qn--) {
char op[2];
scanf("%s", op);
if (op[0] == 'x') {
int i;
ll x00, x01, x10, x11;
scanf("%d%lld%lld%lld%lld", &i, &x00, &x01, &x10, &x11);
//printf("x %d %lld %lld %lld %lld\n", i, x00, x01, x10, x11);
Mat mi(x00, x01, x10, x11);
st.set(sids[i], mi);
}
else { // op[0] == 'g'
int i, j;
scanf("%d%d", &i, &j);
//printf("g %d %d\n", i, j);
Mat ma;
while (gtvs[i] != gtvs[j]) {
Mat mi = st.mul_range(sids[gtes[j]], sids[peis[j]] + 1);
ma = mi * ma;
j = gtvs[j];
}
if (i != j) {
Mat mi = st.mul_range(sids[peis[i]] + 1, sids[peis[j]] + 1);
ma = mi * ma;
}
ma.print();
}
}
return 0;
}