結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 tanzaku
|
| 提出日時 | 2017-03-23 22:57:27 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,878 bytes |
| コンパイル時間 | 3,580 ms |
| コンパイル使用メモリ | 85,696 KB |
| 実行使用メモリ | 70,512 KB |
| 最終ジャッジ日時 | 2024-07-18 01:24:29 |
| 合計ジャッジ時間 | 6,285 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 88 ms
52,924 KB |
| testcase_01 | WA | - |
| testcase_02 | RE | - |
| testcase_03 | AC | 81 ms
52,984 KB |
| testcase_04 | WA | - |
| testcase_05 | RE | - |
| testcase_06 | AC | 77 ms
51,144 KB |
| testcase_07 | AC | 80 ms
52,848 KB |
| testcase_08 | WA | - |
| testcase_09 | RE | - |
| testcase_10 | AC | 77 ms
50,900 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, 20000);
LinkCutTree[] tree = new LinkCutTree[n];
g = new List[n];
for (int i = 0; i < n; i++) {
tree[i] = new LinkCutTree();
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, -1);
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();
LinkCutTree p = 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);
tree[u].link(p);
} else {
throw new RuntimeException();
}
}
in.eof();
}
}
List<Integer>[] g;
int[] par;
void init(int v, int p) {
par[v] = p;
for (int t : g[v]) if (t != p) init(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;
long[] value;
long[] sum;
boolean isSplayRoot() {
return parent == null ||
parent.left != this && parent.right != this;
}
public LinkCutTree() {
this.value = id;
this.sum = id;
}
public void set(long[] value) {
expose();
this.value = value;
update();
}
public long[] sum() {
expose();
// return sum;
if (left == null) return value;
return merge(left.sum, value);
}
private void update() {
sum = value;
if (left != null) sum = merge(left.sum, value);
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;
}
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 LinkCutTree cut() {
expose();
if (left == null) return null;
LinkCutTree p = left;
left = null;
p.parent = null;
update();
return p;
}
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();
}
}
protected void splay() {
final LinkCutTree x = this;
while(!x.isSplayRoot()) {
final LinkCutTree p = x.parent;
if(p.isSplayRoot()) {
// zig step
if(p.left == x) { rotateRight(x); }
else { rotateLeft(x); }
}
else {
final LinkCutTree g = p.parent;
// 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 {
}
}
}