結果
| 問題 | No.2494 Sum within Components |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-10-06 22:10:20 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 593 ms / 2,000 ms |
| コード長 | 20,081 bytes |
| コンパイル時間 | 3,492 ms |
| コンパイル使用メモリ | 98,640 KB |
| 実行使用メモリ | 99,916 KB |
| 最終ジャッジ日時 | 2024-07-26 16:16:11 |
| 合計ジャッジ時間 | 8,474 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 63 ms
37,700 KB |
| testcase_01 | AC | 63 ms
37,836 KB |
| testcase_02 | AC | 63 ms
38,272 KB |
| testcase_03 | AC | 64 ms
37,904 KB |
| testcase_04 | AC | 63 ms
37,828 KB |
| testcase_05 | AC | 64 ms
37,836 KB |
| testcase_06 | AC | 64 ms
37,840 KB |
| testcase_07 | AC | 65 ms
38,004 KB |
| testcase_08 | AC | 64 ms
37,552 KB |
| testcase_09 | AC | 112 ms
40,208 KB |
| testcase_10 | AC | 156 ms
45,996 KB |
| testcase_11 | AC | 123 ms
42,440 KB |
| testcase_12 | AC | 137 ms
42,624 KB |
| testcase_13 | AC | 138 ms
42,432 KB |
| testcase_14 | AC | 355 ms
57,872 KB |
| testcase_15 | AC | 277 ms
52,528 KB |
| testcase_16 | AC | 454 ms
73,044 KB |
| testcase_17 | AC | 546 ms
98,256 KB |
| testcase_18 | AC | 593 ms
99,916 KB |
| testcase_19 | AC | 566 ms
75,024 KB |
ソースコード
import java.util.*;
import java.io.*;
import java.sql.Array;
import java.util.stream.*;
import java.util.function.*;
class Main implements Runnable
{
void solve()
{
int N = in.nextInt() , M = in.nextInt();
long [] A = in.LongArray(N);
UnionFind uf = new UnionFind(N);
for(int i = 0 ; i < M ; i ++ )
{
int u = in.nextInt() , v = in.nextInt();
--u;--v;
uf.unite(u , v);
}
List<List<Integer>> g = uf.Groups();
long ans = 1 ;
for(int i = 0 ; i < g.size() ; i ++ )
{
long sum = 0 ;
for(int v : g.get(i)) sum = ((sum + A[v])% MOD9);
long tot = power(sum , g.get(i).size()) % MOD9;
ans = (ans * tot) % MOD9;
}
out.print(ans % MOD9);
}
long power(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) != 0) {
res = (res * a) % MOD9;
}
a = (a * a) % MOD9;
b >>= 1;
}
return res;
}
double dist_m(ip p1 , ip p2) { return Math.abs(p1.fi - p2.fi) + Math.abs(p1.se - p2.se) ; }
double dist_u(ip p1 , ip p2) { return Math.sqrt(Math.pow(p1.fi - p2.fi , 2) + Math.pow(p1.se - p2.se, 2)); }
public static void main(String[] args)
{
new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();
}
public void run()
{
solve();
out.flush();
}
record ip(int fi , int se) { public String toString() { return fi +" "+ se ;} }
record lp(long fi , long se) { public String toString() { return fi +" "+ se ;} }
public double dist(lp p1 , lp p2) { return Math.sqrt((p1.fi - p2.fi) * (p1.fi - p2.fi) + (p1.se - p2.se) * (p1.se - p2.se)); }
public int max(int ... a) { int max = -1 ; for(int p : a) max = Math.max(max , p); return max; }
public int min(int ... a) { int min = Integer.MAX_VALUE ; for(int p : a) min = Math.min(min , p); return min; }
public long max(long ... a) { long max = -1 ; for(long p : a) max = Math.max(max , p); return max; }
public long min(long ... a) { long min = Long.MAX_VALUE ; for(long p : a) min = Math.min(min , p); return min; }
public int sum(int ... a) { int sum = 0 ; for(int p : a) sum += p ; return sum ;}
public long sum(long ... a) { long sum = 0 ; for(long p : a) sum += p ; return sum ;}
public int abs(int a , int b) { return (int) Math.abs(a - b) ; }
public long abs(long a , long b) { return (long) Math.abs(a - b) ; }
public int pow(int a , int b) { return (int) Math.pow(a , b) ; }
public long pow(long a , long b) { return (long) Math.pow(a , b) ; }
public long rec(long a) { return a == 1 ? 1 : a * rec(a - 1); }
public long [] recmod(int a , long MOD) { long [] recMod = new long[1 << 17] ; recMod[1] = 1 ; for(int i = 2 ; i < (1 << 17) ; i ++ ) recMod[i] = (recMod[i - 1] * i) % MOD9; return recMod; }
public int [] rev(int [] a) { int [] r = new int[a.length] ; int idx = a.length ; for(int p : a) r[--idx] = p ; return r ; }
public long [] rev(long [] a) { long [] r = new long[a.length] ; int idx = a.length ; for(long p : a) r[--idx] = p ; return r ; }
public int gcd(int a, int b) { return b == 0 ? a: gcd(b, a % b); }
public int lcm(int a, int b) { return a / gcd(a, b) * b; }
public long gcd(long a, long b) { return b == 0 ? a: gcd(b, a % b); }
public long lcm(long a, long b) { return a / gcd(a, b) * b; }
public int gcd(int ... a) { int gcd = 0 ; for(int p : a) gcd = gcd(gcd , p) ; return gcd ; }
public long gcd(long ... a) { long gcd = 0L ; for(long p : a) gcd = gcd(gcd , p) ; return gcd ; }
public int lcm(int ... a) { int lcm = 1 ; for(int p : a) lcm = lcm(lcm , p) ; return lcm ; }
public long lcm(long ... a) { long lcm = 1 ; for(long p : a) lcm = lcm(lcm , p) ; return lcm ; }
public char upper(char c) { return (char)('A' + (c - 'a')); }
public char lower(char c) { return (char)('a' + (c - 'A')); }
public String yn(boolean a) { return a ? yes : no ; }
public String rev(String a) { return new StringBuilder(a).reverse().toString(); }
public void fill(int [] a , int v) { Arrays.fill(a , v); }
public void fill(long [] a , long v) { Arrays.fill(a , v); }
public void fill(int [][] a , int v) { for(int [] aa : a) fill(aa , v) ; }
public void fill(long [][] a , long v) { for(long [] aa : a) fill(aa , v) ; }
public void fill(int [][][] a , int v) { for(int [][] aa : a) fill(aa , v); }
public void fill(long [][][] a , long v) { for(long [][] aa : a) fill(aa , v); }
public int [] copy(int [] a) { return Arrays.copyOf(a , a.length); }
public long [] copy(long [] a) { return Arrays.copyOf(a , a.length); }
public String bin(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; }
public void debug(int [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(long [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(double [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(String [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(char [] a) { out.println(Arrays.toString(a)); fl();}
public void debug(boolean [] a) { char [] c = conv(a); debug(c); fl();}
public void debug(int [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(long [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(double [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(String [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(char [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}
public void debug(boolean [][] a) { char [][] c = new char [a.length][a[0].length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = conv(a[i]) ; debug(c); fl();}
private char [] conv(boolean [] a) { char [] c = new char[a.length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = a[i] ? 'O' : 'X' ; return c ; }
private void fl() { out.flush(); }
PrintWriter out = new PrintWriter(System.out);
In in = new In();
static final long MOD7 = 1000000007;
static final long MOD9 = 998244353;
static final int inf = (1 << 30);
static final long lnf = (1L << 60);
final String yes = "Yes";
final String no = "No" ;
final char [] dir = {'U','R','D','L'};
final int [] dy4 = {-1,0,1,0};
final int [] dx4 = {0,1,0,-1};
final int [] dy8 = {-1,-1,-1,0,1,1,1,0};
final int [] dx8 = {-1,0,1,1,1,0,-1,-1};
}
class LazySegmentTree {
final long[] Dat;
final long[] Laz;
final int N;
final long E0;
final long E1;
final LongBinaryOperator F;
final LongBinaryOperator G;
final LongBinaryOperator H;
final LongBinaryOperator P;
final int[] Stack = new int[64];
//初期配列 , dat(関与しない値) , lazy(関与しない値) , dat() , dat&lazy() , lazy() , lazy*len()
public LazySegmentTree(int n, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p) {
this.E0 = e0;
this.E1 = e1;
this.F = f; this.G = g; this.H = h; this.P = p;
int k = 1;
while (k <= n) k <<= 1;
this.Dat = new long[k << 1];
this.Laz = new long[k << 1];
this.N = k;
Arrays.fill(Dat, E0);
Arrays.fill(Laz, E1);
}
public LazySegmentTree(long[] src, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p) {
this(src.length, e0, e1, f, g, h, p);
build(src);
}
private void build(long[] src) {
System.arraycopy(src, 0, Dat, N, src.length);
for (int i = N - 1; i > 0; i--) Dat[i] = F.applyAsLong(Dat[i << 1 | 0], Dat[i << 1 | 1]);
}
public void update(int l, int r, long v) {
if (l >= r) return;
int m = updown(l, r);
l += N; r += N;
for (; l < r; l >>= 1, r >>= 1) {
if ((l & 1) != 0) {Laz[l] = H.applyAsLong(Laz[l], v); l++;}
if ((r & 1) != 0) {r--; Laz[r] = H.applyAsLong(Laz[r], v);}
}
for (int i = 0; i < m; i++) {
int k = Stack[i];
Dat[k] = F.applyAsLong(calcDat(k << 1 | 0), calcDat(k << 1 | 1));
}
}
public long query(int i) {
int k = 1;
int l = 0, r = N;
while (k < N) {
int kl = k << 1 | 0;
int kr = k << 1 | 1;
Dat[k] = F.applyAsLong(calcDat(kl), calcDat(kr));
int m = (l + r) >> 1;
if (m > i) {r = m; k = kl;}
else {l = m; k = kr;}
}
return Dat[k];
}
public long query(int l, int r) {
if (l >= r) return E0;
updown(l, r);
long resL = E0, resR = E0;
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if ((l & 1) != 0) resL = F.applyAsLong(resL, calcDat(l++));
if ((r & 1) != 0) resR = F.applyAsLong(calcDat(--r), resR);
}
return F.applyAsLong(resL, resR);
}
private int updown(int l, int r) {
if (l >= r) return 0;
int i = 0;
int kl = l + N, kr = r + N;
for (int x = kl / (kl & -kl) >> 1, y = kr / (kr & -kr) >> 1; 0 < kl && kl < kr; kl >>= 1, kr >>= 1) {
if (kl <= x) Stack[i++] = kl;
if (kr <= y) Stack[i++] = kr;
}
for (; kl > 0; kl >>= 1) Stack[i++] = kl;
int m = i;
while (i > 0) calcDat(Stack[--i]);
return m;
}
private long calcDat(int k) {
long lz = Laz[k];
if (lz != E1) {
int w = N / Integer.highestOneBit(k);
Dat[k] = G.applyAsLong(Dat[k], P.applyAsLong(lz, w));
if (k < N) {
int l = k << 1 | 0, r = k << 1 | 1;
Laz[l] = H.applyAsLong(Laz[l], lz);
Laz[r] = H.applyAsLong(Laz[r], lz);
}
Laz[k] = E1;
}
return Dat[k];
}
void debug()
{
for(int i = Dat.length - N ; i < Dat.length - 1; i ++ )
{
System.out.print(Dat[i]+" ");
}
System.out.println();
}
}
final class WaveletMatrix {
private final int[][] data;
private final int n, bit;
WaveletMatrix(int[] d, int bit) {
n = d.length;
this.bit = bit;
int[] dat = d.clone();
data = new int[bit][n];
int[] que = new int[n];
for (int k = bit - 1; k >= 0; k--) {
int que1 = 0, que2 = n;
for (int i = 0; i < n; i++) {
if ((data[k][i] = (dat[i] >> k) & 1) == 1)
que[--que2] = dat[i];
else
que[que1++] = dat[i];
}
for (int i = 0; i < que1; i++)
dat[i] = que[i];
for (int i = n - 1, j = que1; i >= que1; i--, j++)
dat[j] = que[i];
for (int i = 1; i < n; i++)
data[k][i] += data[k][i - 1];
}
}
WaveletMatrix(int[] dat) {
this(dat, 31);
}
private final int get(int bi, int id) {
if (id == 0)
return data[bi][0];
return data[bi][id] - data[bi][id - 1];
}
final int access(int idx) {
int ans = 0;
for (int k = bit - 1; k >= 0; k--) {
if (get(k, idx) == 1) {
ans |= 1 << k;
idx = zer(k, n) + one(k, idx);
} else
idx -= data[k][idx];
}
return ans;
}
private final int one(int bi, int l) {
if (l == 0)
return 0;
return data[bi][l - 1];
}
private final int zer(int bi, int l) {
return l - one(bi, l);
}
private final int sum(int bi, int l, int r) {
return one(bi, r) - one(bi, l);
}
public final int kth_smallest(int l, int r, int kth) {
int ans = 0;
for (int k = bit - 1; k >= 0; k--) {
final int s = r - l - sum(k, l, r);
if (kth < s) {
l = zer(k, l);
r = l + s;
} else {
kth -= s;
ans |= 1 << k;
final int ran = r - l - s;
l = zer(k, n) + one(k, l);
r = l + ran;
}
}
return ans;
}
public final int kth_largest(int l, int r, int kth) {
return kth_smallest(l, r, r - l - kth);
}
public final int count_lower(int l, int r, int lower) {
int ans = 0;
for (int k = bit - 1; k >= 0; k--) {
final int s = r - l - sum(k, l, r);
if (((lower >> k) & 1) == 1) {
ans += s;
final int ran = r - l - s;
l = zer(k, n) + one(k, l);
r = l + ran;
} else {
l = zer(k, l);
r = l + s;
}
}
return ans;
}
public final int count_upper(int l, int r, int upper) {
return r - l - count_lower(l, r, upper + 1);
}
public final int count(int l, int r, int x) {
return count_lower(l, r, x + 1) - count_lower(l, r, x);
}
public final int next_value(int l, int r, int upper) {
final int cnt = count_lower(l, r, upper + 1);
return kth_smallest(l, r, cnt);
}
public final int perv_value(int l, int r, int lower) {
final int cnt = count_upper(l, r, lower - 1);
return kth_largest(l, r, cnt);
}
}
class UnionFind
{
private int [] rank , parents , size , data , edges;
private int groups ;
private BinaryOperator<Integer> op ;
private static BinaryOperator<Integer> def_op = (a, b) -> a;
UnionFind(int N) { this(N , def_op) ; }
UnionFind(int N , BinaryOperator<Integer> op)
{
this.rank = new int[N];
this.parents = new int[N];
this.size = new int[N];
this.data = new int[N];
this.edges = new int[N];
this.groups = N ;
for(int i = 0 ; i < N ; i ++ )
{
parents[i] = i ;
rank[i] = 0 ;
size[i] = 1 ;
data[i] = i ;
}
this.op = op ;
}
int Group() { return this.groups ; }
int Edge(int x) { return edges[root(x)] ; }
int Op(int x) { return data[root(x)] ; }
int Size(int x) { return size[root(x)] ; }
int root(int x)
{
if(x == parents[x]) return x ;
else parents[x] = root(parents[x]);
return parents[x];
}
boolean same(int x , int y) { return root(x) == root(y) ; }
void unite(int l , int r)
{
int left = root(l);
int right = root(r);
int parent = -1 , child = -1 ;
if(left == right) { ++ edges[right]; return ; }
parent = rank[left] > rank[right] ? left : right;
child = rank[left] > rank[right] ? right : left ;
--groups;
parents[child] = parent ;
rank[child] ++ ;
size[parent] += size[child] ;
edges[parent] += edges[child] + 1 ;
data[parent] = op.apply(data[child] , data[parent]);
}
List<List<Integer>> Groups() {
List<List<Integer>> Group = new ArrayList<>();
Map<Integer,List<Integer>> mp = new HashMap<>();
for(int i = 0 ; i < parents.length ; i ++ )
{
int par = root(i);
if(!mp.containsKey(par)) mp.put(par , new ArrayList<>());
mp.get(par).add(i);
}
for(List<Integer> lists : mp.values()) Group.add(new ArrayList<>(lists));
return Group;
}
}
class In
{
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
}else{
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++]; else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private boolean hasNext() {
while(hasNextByte() && !isPrintableChar(buffer[ptr])) {
ptr++;
}
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while(isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while(true){
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
}else if(b == -1 || !isPrintableChar(b)){
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public char nextChar() {
return next().charAt(0);
}
public int [] IntArray(int n) {
final int [] Array = new int [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextInt();
}
return Array;
}
public int [][] IntArray(int n , int m) {
final int [][] Array = new int [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = IntArray(m);
}
return Array;
}
public long [] LongArray(int n) {
final long [] Array = new long [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = nextLong();
}
return Array;
}
public long [][] LongArray(int n , int m) {
final long [][] Array = new long [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = LongArray(m);
}
return Array;
}
public String [] StringArray(int n) {
final String [] Array = new String [n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next();
}
return Array;
}
public char [] CharArray(int n) {
final char [] Array = new char[n];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().charAt(0);
}
return Array;
}
public char [][] CharArray(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
Array[i] = next().toCharArray();
}
return Array;
}
public char [][] CharArray2(int n , int m) {
final char [][] Array = new char [n][m];
for(int i = 0 ; i < n ; i ++ ) {
for(int j = 0 ; j < m ; j ++ ) {
Array[i][j] = next().charAt(0);
}
}
return Array;
}
public List<Integer> [] Graph(int n) {
@SuppressWarnings("unchecked")
List<Integer> [] G = new ArrayList[n];
for(int i = 0 ; i < n ; i ++ ) {
G[i] = new ArrayList<>();
}
return G ;
}
}