結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 tanzaku
|
| 提出日時 | 2017-04-09 13:05:13 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 1,746 ms / 2,000 ms |
| コード長 | 9,001 bytes |
| コンパイル時間 | 5,892 ms |
| コンパイル使用メモリ | 86,600 KB |
| 実行使用メモリ | 122,052 KB |
| 最終ジャッジ日時 | 2023-11-09 22:27:12 |
| 合計ジャッジ時間 | 14,040 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 108 ms
56,560 KB |
| testcase_01 | AC | 737 ms
70,160 KB |
| testcase_02 | AC | 1,553 ms
100,424 KB |
| testcase_03 | AC | 104 ms
54,616 KB |
| testcase_04 | AC | 751 ms
70,156 KB |
| testcase_05 | AC | 1,447 ms
98,304 KB |
| testcase_06 | AC | 104 ms
56,460 KB |
| testcase_07 | AC | 106 ms
56,432 KB |
| testcase_08 | AC | 883 ms
72,532 KB |
| testcase_09 | AC | 1,746 ms
122,052 KB |
| testcase_10 | AC | 110 ms
56,516 KB |
ソースコード
import java.io.*;
import java.util.*;
public class _p1317_Validate {
public static void main(String[] args) throws IOException {
new _p1317_Validate().solve();
}
static int mod = (int)1e9+7;
void solve() throws IOException {
try (final InputValidator in = new InputValidator(System.in)) {
int n = in.nextInt(1, 100000);
LinkCutTree[] tree = new LinkCutTree[n];
g = new List[n];
for (int i = 0; i < n; i++) {
tree[i] = new LinkCutTree(i);
g[i] = new ArrayList<>();
}
in.newLine();
UnionFind uf = new UnionFind(n);
int[][] es = new int[n-1][];
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt(0, n - 1);
in.space();
int b = in.nextInt(0, n - 1);
in.newLine();
es[i] = new int[]{a,b};
uf.union(a, b);
g[a].add(b);
g[b].add(a);
}
par = new int[n];
init(0);
for (int[] e : es) {
if (par[e[0]] == e[1]) {
int tmp = e[0];
e[0] = e[1];
e[1] = tmp;
}
tree[e[1]].link(tree[e[0]]);
}
int q = in.nextInt(1, 20000);
in.newLine();
while (q-- > 0) {
char c = in.nextChar();
in.space();
if (c == 'x') {
int i = in.nextInt(0, n - 2); in.space();
int x00 = in.nextInt(0, 1000); in.space();
int x01 = in.nextInt(0, 1000); in.space();
int x10 = in.nextInt(0, 1000); in.space();
int x11 = in.nextInt(0, 1000); in.newLine();
tree[es[i][1]].set(new long[]{x00,x01,x10,x11});
} else if (c == 'g') {
int u = in.nextInt(0, n - 1); in.space();
int v = in.nextInt(0, n - 1); in.newLine();
long[] tmp = tree[u].value;
tree[u].expose();
tree[u].cut();
tree[u].set(id);
tree[v].expose();
long[] ans = tree[v].sum;
System.out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);
tree[u].set(tmp);
if (par[u] >= 0) {
tree[u].link(tree[par[u]]);
}
} else {
throw new RuntimeException();
}
}
in.eof();
}
}
void debug(LinkCutTree t, String path) {
if (t != null) {
debug(t.left, path + "L");
dump(t.value, t.sum, t.index, path);
debug(t.right, path + "R");
}
}
List<Integer>[] g;
int[] par;
void init(int root) {
int[] st = new int[g.length];
int sp = 0;
st[sp++] = root;
par[root] = -1;
// dump("par", v, p);
while (sp != 0) {
int v = st[--sp];
for (int t : g[v]) if (t != par[v]) {
st[sp++] = t;
par[t] = v;
}
}
}
static long[] merge(long[] l, long[] r) {
long[] res = new long[4];
res[0] = (l[0] * r[0] + l[1] * r[2]) % mod;
res[1] = (l[0] * r[1] + l[1] * r[3]) % mod;
res[2] = (l[2] * r[0] + l[3] * r[2]) % mod;
res[3] = (l[2] * r[1] + l[3] * r[3]) % mod;
return res;
}
final static long[] id = new long[]{1,0,0,1,};
static class LinkCutTree {
LinkCutTree parent;
LinkCutTree left;
LinkCutTree right;
boolean rev;
long[] value;
long[] sum;
final int index;
void debug() {
dump(value, sum, index);
}
boolean isSplayRoot() {
return parent == null ||
parent.left != this && parent.right != this;
}
public LinkCutTree(final int index) {
this.index = index;
this.value = id;
this.sum = id;
}
public void set(long[] value) {
expose();
this.value = value;
update();
}
/**
* expose後はrightは必ずnullなので単にsumを返すだけでよい。
*/
public long[] sum() {
expose();
return sum;
}
private void update() {
sum = value;
if (left != null) sum = merge(left.sum, sum);
if (right != null) sum = merge(sum, right.sum);
}
public static LinkCutTree lca(LinkCutTree u, LinkCutTree v) {
if(u == v) return u;
LinkCutTree a = u.findRoot();
LinkCutTree b = v.findRoot();
if(a != b) {
return null;
}
u.splay();
if(u.parent != null && u.parent.left != u && u.parent.right != u) {
return u.parent;
}
return u;
}
public void evert() {
expose();
rev = !rev;
}
/**
* thisから根までのパスがsplay treeの形で構成されている状態になる
* leftはthisの親
* rightは必ずnull
* なので、自分より根から遠いノードは存在しない
*/
private void expose() {
LinkCutTree x = this;
LinkCutTree r = null;
for(LinkCutTree p = x; p != null; p = p.parent) {
p.splay();
p.right = r;
r = p;
}
x.splay();
}
public LinkCutTree findRoot() {
LinkCutTree v = this;
v.expose();
while(v.left != null)
v = v.left;
v.splay();
return v;
}
public void cut() {
expose();
if (left == null) return;
LinkCutTree p = left;
left = null;
p.parent = null;
// while (p.right != null) p = p.right;
update();
p.splay();
}
public void link(LinkCutTree p) {
if (p == null) return;
expose();
p.expose();
parent = p;
p.right = this;
p.update();
}
static void rotateRight(LinkCutTree x) {
final LinkCutTree p = x.parent;
final LinkCutTree g = p.parent;
p.left = x.right;
if(x.right != null) { x.right.parent = p; }
p.parent = x;
x.right = p;
x.parent = g;
p.update();
x.update();
if(g != null) {
if(g.left == p) g.left = x;
else if(g.right == p) g.right = x;
g.update();
}
}
static void rotateLeft(LinkCutTree x) {
final LinkCutTree p = x.parent;
final LinkCutTree g = p.parent;
p.right = x.left;
if(x.left != null) { x.left.parent = p; }
p.parent = x;
x.left = p;
x.parent = g;
p.update();
x.update();
if(g != null) {
if(g.left == p) g.left = x;
else if(g.right == p) g.right = x;
g.update();
}
}
private void pushDown() {
if (rev) {
LinkCutTree t = left; left = right; right = t;
if (left != null) left.rev = !left.rev;
if (right != null) right.rev = !right.rev;
rev = false;
}
}
protected void splay() {
final LinkCutTree x = this;
while(!x.isSplayRoot()) {
final LinkCutTree p = x.parent;
if(p.isSplayRoot()) {
p.pushDown();
x.pushDown();
// zig step
if(p.left == x) { rotateRight(x); }
else { rotateLeft(x); }
}
else {
final LinkCutTree g = p.parent;
g.pushDown();
p.pushDown();
x.pushDown();
// zig-zig step / zig-zag step
if(g.left == p) {
if(p.left == x) { rotateRight(p); rotateRight(x); }
else { rotateLeft(x); rotateRight(x); }
}
else {
if(p.left == x) { rotateRight(x); rotateLeft(x); }
else { rotateLeft(p); rotateLeft(x); }
}
}
}
}
}
static class UnionFind {
private int[] data;
public UnionFind(int size) {
data = new int[size];
clear();
}
public void clear() {
Arrays.fill(data, -1);
}
public int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); }
public void union(int x, int y) {
if((x = root(x)) == (y = root(y))) {
throw new RuntimeException();
}
if(data[y] < data[x]) { final int t = x; x = y; y = t; }
data[x] += data[y];
data[y] = x;
}
public boolean same(int x, int y) { return root(x) == root(y); }
public int size(int x) { return -data[root(x)]; }
}
// for debug
static void dump(Object... o) {
System.err.println(Arrays.deepToString(o));
}
static class InputValidator implements Closeable {
final InputStream in;
final int NO_BUFFER = -2;
int buffer;
public InputValidator(final InputStream in) {
this.in = in;
buffer = NO_BUFFER;
}
public char nextChar() throws IOException {
int res = read();
check(Character.isLetterOrDigit(res));
return (char)res;
}
int read() throws IOException {
final int res = buffer == NO_BUFFER ? in.read() : buffer;
buffer = NO_BUFFER;
return res;
}
void unread(int ch) throws IOException {
buffer = ch;
}
// [low, high]
long nextLong(long low, long high) throws IOException {
long val = 0;
int ch = -1;
boolean read = false;
while (true) {
ch = read();
if (!Character.isDigit(ch)) break;
read = true;
val = val * 10 + ch - '0';
check(val <= high);
}
check(read);
check(ch >= 0);
check(val >= low);
unread(ch);
return val;
}
int nextInt(int low, int high) throws IOException { return (int)nextLong(low, high); }
int[] nextInts(int n, int low, int high) throws IOException {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt(low, high);
if (i + 1 != n) space();
}
newLineOrEOF();
return res;
}
void space() throws IOException { int ch = read(); check(ch == ' '); }
void newLine() throws IOException {
int ch = read();
if (ch == '\r') ch = read();
check(ch == '\n');
}
void newLineOrEOF() throws IOException { int ch = read(); check(ch == '\r' || ch == '\n' || ch < 0); }
void eof() throws IOException { int ch = read(); check(ch < 0); }
void check(boolean b) { if (!b) throw new RuntimeException(); }
@Override
public void close() throws IOException {
}
}
}