結果

問題 No.1207 グラフX
ユーザー ks2m
提出日時 2020-08-30 14:01:52
言語 Java
(openjdk 23)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,424 bytes
コンパイル時間 3,745 ms
コンパイル使用メモリ 78,372 KB
実行使用メモリ 114,320 KB
最終ジャッジ日時 2024-12-27 15:27:01
合計ジャッジ時間 63,105 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static List<List<Hen>> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] sa = br.readLine().split(" ");
int n = Integer.parseInt(sa[0]);
int m = Integer.parseInt(sa[1]);
int x = Integer.parseInt(sa[2]);
list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
UnionFind uf = new UnionFind(n);
List<Hen> hens = new ArrayList<>();
for (int i = 0; i < m; i++) {
sa = br.readLine().split(" ");
Hen h = new Hen();
h.x = Integer.parseInt(sa[0]) - 1;
h.y = Integer.parseInt(sa[1]) - 1;
h.z = Integer.parseInt(sa[2]);
if (!uf.same(h.x, h.y)) {
uf.union(h.x, h.y);
list.get(h.x).add(h);
list.get(h.y).add(h);
hens.add(h);
}
}
br.close();
dfs(0, -1);
int mod = 1000000007;
long ans = 0;
for (Hen h : hens) {
long cnt = (long) h.c * (n - h.c) % mod;
ans += power(x, h.z, mod) * cnt;
ans %= mod;
}
System.out.println(ans);
}
static int dfs(int cur, int p) {
int ret = 1;
List<Hen> nexts = list.get(cur);
for (Hen h : nexts) {
int next = h.x;
if (next == cur) {
next = h.y;
}
if (next == p) {
continue;
}
h.c = dfs(next, cur);
ret += h.c;
}
return ret;
}
static class Hen {
int x, y, z, c;
}
static long power(long x, long n, int m) {
if (n == 0) {
return 1;
}
long val = power(x, n / 2, m);
val = val * val % m;
if (n % 2 == 1) {
val = val * x % m;
}
return val;
}
static class UnionFind {
int[] parent, size;
int num = 0; //
UnionFind(int n) {
parent = new int[n];
size = new int[n];
num = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
size[py] += size[px];
num--;
}
}
int find(int x) {
if (parent[x] == x) {
return x;
}
parent[x] = find(parent[x]);
return parent[x];
}
/**
* xy
*/
boolean same(int x, int y) {
return find(x) == find(y);
}
/**
* x
*/
int size(int x) {
return size[find(x)];
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0