結果
| 問題 | No.762 PDCAパス |
| ユーザー |
 k_6101
|
| 提出日時 | 2019-12-10 13:42:08 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 893 ms / 2,000 ms |
| コード長 | 8,510 bytes |
| コンパイル時間 | 2,808 ms |
| コンパイル使用メモリ | 91,188 KB |
| 実行使用メモリ | 99,324 KB |
| 最終ジャッジ日時 | 2024-06-24 01:48:01 |
| 合計ジャッジ時間 | 21,980 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 124 ms
53,804 KB |
| testcase_01 | AC | 121 ms
53,784 KB |
| testcase_02 | AC | 122 ms
53,528 KB |
| testcase_03 | AC | 127 ms
54,012 KB |
| testcase_04 | AC | 121 ms
53,364 KB |
| testcase_05 | AC | 113 ms
52,936 KB |
| testcase_06 | AC | 117 ms
53,024 KB |
| testcase_07 | AC | 124 ms
53,512 KB |
| testcase_08 | AC | 128 ms
53,936 KB |
| testcase_09 | AC | 122 ms
53,664 KB |
| testcase_10 | AC | 117 ms
52,912 KB |
| testcase_11 | AC | 112 ms
52,688 KB |
| testcase_12 | AC | 124 ms
53,528 KB |
| testcase_13 | AC | 122 ms
53,272 KB |
| testcase_14 | AC | 123 ms
53,588 KB |
| testcase_15 | AC | 133 ms
54,116 KB |
| testcase_16 | AC | 131 ms
53,476 KB |
| testcase_17 | AC | 127 ms
52,996 KB |
| testcase_18 | AC | 126 ms
53,548 KB |
| testcase_19 | AC | 131 ms
53,976 KB |
| testcase_20 | AC | 119 ms
52,812 KB |
| testcase_21 | AC | 126 ms
53,508 KB |
| testcase_22 | AC | 641 ms
62,276 KB |
| testcase_23 | AC | 629 ms
61,536 KB |
| testcase_24 | AC | 874 ms
96,372 KB |
| testcase_25 | AC | 893 ms
99,324 KB |
| testcase_26 | AC | 676 ms
66,492 KB |
| testcase_27 | AC | 676 ms
66,560 KB |
| testcase_28 | AC | 863 ms
80,460 KB |
| testcase_29 | AC | 831 ms
81,232 KB |
| testcase_30 | AC | 808 ms
80,332 KB |
| testcase_31 | AC | 793 ms
78,292 KB |
| testcase_32 | AC | 792 ms
76,992 KB |
| testcase_33 | AC | 829 ms
75,020 KB |
| testcase_34 | AC | 843 ms
75,368 KB |
| testcase_35 | AC | 811 ms
75,228 KB |
| testcase_36 | AC | 733 ms
66,304 KB |
| testcase_37 | AC | 762 ms
67,740 KB |
| testcase_38 | AC | 734 ms
66,284 KB |
| testcase_39 | AC | 723 ms
67,492 KB |
| testcase_40 | AC | 770 ms
67,816 KB |
ソースコード
import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
import static java.util.Comparator.*;
public class Main {
public static void main(String[] args) {
PrintWriter out = new PrintWriter(System.out);
Solver solver = new Solver(System.in, out);
solver.solve();
out.close();
}
}
class Solver {
Scanner sc;
PrintWriter out;
public Solver(InputStream in, PrintWriter out) {
sc = new Scanner(in);
this.out = out;
}
// ==================================================================
long MOD = 1000000007;
char[] check = { 'P', 'D', 'C', 'A' };
Graph G = new Graph();
int N;
char[] C;
int[] used;
long[][] mem;
long calc(int now, int cnt) {
// out.println("開始 now = " + now + " cnt = " + cnt);
if(cnt == 4) return 1;
if(mem[now][cnt] != -1) return mem[now][cnt];
long ans = 0;
for(int key : G.get(now)) {
if(used[key] > 0) continue;
if(check[cnt] != C[key]) continue;
used[key] = 1;
ans += calc(key, cnt + 1);
ans %= MOD;
used[key] = 0;
}
// out.println("終了 now = " + now + " cnt = " + cnt + " --> ans = " + ans);
return mem[now][cnt] = ans;
}
public void solve() {
N = Integer.parseInt(sc.next());
used = new int[N];
mem = new long[N][4];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 4; j++) {
mem[i][j] = -1;
}
}
int M = Integer.parseInt(sc.next());
C = sc.next().toCharArray();
int u, v;
for (int i = 0; i < M; i++) {
u = Integer.parseInt(sc.next()) - 1;
v = Integer.parseInt(sc.next()) - 1;
if(C[u] == 'P' && C[v] != 'D') continue;
else if(C[u] == 'D' && (C[v] != 'P' && C[v] != 'C')) continue;
else if(C[u] == 'C' && (C[v] != 'D' && C[v] != 'A')) continue;
else if(C[u] == 'A' && C[v] != 'C') continue;
G.add(u, v);
G.add(v, u);
}
long ans = 0;
for (int i = 0; i < N; i++) {
if(C[i] == 'P' && G.contains(i)) {
ans += calc(i, 1);
ans %= MOD;
}
}
out.println(ans);
}
// -----------------------------------------
// 重みなし グラフのリンクリスト
class Graph {
// 頂点に紐づく頂点のリスト
private Map<Integer, List<Integer>> data = new HashMap<Integer, List<Integer>>();
// // 全ての頂点のセット
// private Set<Integer> point = new TreeSet<>();
// 頂点と頂点の繋がりを追加する
void add(int from, int to) {
List<Integer> list = data.get(from);
if(list == null) {
list = new ArrayList<Integer>();
data.put(from, list);
}
list.add(to);
// point.add(from);
// point.add(to);
}
// 始点から終点が繋がっていれば切る
void del(int from, int to) {
List<Integer> list = data.get(from);
if(list == null) {
return;
}
if(list.contains(to)) {
list.remove((Object)to);
}
}
// 指定された頂点に紐づく、頂点のリストを返す
List<Integer> get(int key) {
return data.get(key);
}
// 頂点 key が登録されているか？
boolean contains(int key) {
return data.containsKey(key);
}
// 頂点のセットを返す
Set<Integer> keySet() {
return data.keySet();
}
// 頂点 key_1 と 頂点 key_2 がつながっていれば true を返す
boolean isConnect(int key_1, int key_2) {
List<Integer> list = data.get(key_1);
if(list == null) return false;
else return list.contains(key_2);
}
// 指定された頂点から、すべての頂点への距離を返す(DFS O(N)） → 返り値が 終点と距離のペア のリスト
List<PP> distList(int key) {
List<PP> dist = new ArrayList<>(); // 頂点と距離のペアのリスト
Set<Integer> mark = new HashSet<>(); // 処理したら入れる
Stack<PP> stack = new Stack<>(); // スタックの宣言
stack.push(new PP(key, 0)); // スタートをスタックに保存
while(!stack.isEmpty()) {
PP wk = stack.pop(); // スタックから次の頂点を取得
int pp = wk.getKey();
int dd = wk.getVal();
mark.add(pp); // 通過マーク
dist.add(new PP(pp, dd)); // 距離を登録
List<Integer> list = get(pp); // つながっている頂点のリストを取得
for(int next : list) {
if(mark.contains(next)) continue;
stack.push(new PP(next, dd + 1));
}
}
return dist;
}
// 指定された頂点から、すべての頂点への距離を返す(DFS O(N)） → 返り値は配列
int[] distV(int key) {
int[] dist = new int[data.keySet().size()+1]; // [頂点] = 距離
Arrays.fill(dist, -1); // 届かない場合 -1
Set<Integer> mark = new HashSet<>(); // 処理したら入れる
Stack<PP> stack = new Stack<>(); // スタックの宣言
stack.push(new PP(key, 0)); // スタートをスタックに保存
while(!stack.isEmpty()) {
PP wk = stack.pop(); // スタックから次の頂点を取得
int pp = wk.getKey();
int dd = wk.getVal();
mark.add(pp); // 通過マーク
dist[pp] = dd; // 距離を登録
List<Integer> list = get(pp); // つながっている頂点のリストを取得
for(int next : list) {
if(mark.contains(next)) continue;
stack.push(new PP(next, dd + 1));
}
}
return dist;
}
Map<Integer, Integer> mapCnt = new HashMap<>(); // 項番（何番目に訪れたか）
Map<Integer, Integer> mapLow = new HashMap<>(); // 初期値は項番、つながっている先の項番が小さければコピーする
// mapCnt > mapLow なら閉路に含まれる頂点
Set<Integer> mark = new HashSet<>(); // 処理したら入れる
int number;
// mapCnt, mapLow を設定する
int bridgeDfs(int now, int pre) {
// prn("bridgeDfs now = " + now + " number = " + number);
mark.add(now);
mapCnt.put(now, number);
mapLow.put(now, number);
int low;
for(int next : get(now)) {
if(next == pre) continue;
if(mark.contains(next)) {
if(mapLow.get(now) > mapLow.get(next)) {
// prn(" mapLow[" + now + "] = " + mapLow.get(now)
// + " > mapLow[" + next + "] = " + mapLow.get(next));
mapLow.put(now, mapLow.get(next));
}
continue;
}
number++;
low = bridgeDfs(next, now);
if(mapLow.get(now) > low) {
mapLow.put(now, low);
}
}
return mapLow.get(now);
}
// 橋の数を返す 先頭の頂点番号を引数とする
int bridgeCnt(int start) {
mapCnt.clear();
mapLow.clear();
mark.clear();
number = 0;
bridgeDfs(start, start);
int ans = 0;
for(int key : mapCnt.keySet()) {
if(mapCnt.get(key) == mapLow.get(key)) {
ans++;
}
}
return ans - 1;
}
// ダンプ
void dump(PrintWriter out) {
for(int key : data.keySet()) {
out.print(key + " : ");
for(int val : data.get(key)) {
out.print(val + " ");
}
out.println("");
}
}
}
// Set に入れるなら PPKEY を使う！
static class PP{
public int key, val;
public PP(int key, int val) {
this.key = key;
this.val = val;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
}
// ==================================================================
}