結果
問題 | No.762 PDCAパス |
ユーザー |
![]() |
提出日時 | 2019-03-20 16:15:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 2,711 bytes |
コンパイル時間 | 656 ms |
コンパイル使用メモリ | 75,688 KB |
実行使用メモリ | 19,780 KB |
最終ジャッジ日時 | 2024-09-19 00:44:04 |
合計ジャッジ時間 | 4,586 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘int ncrset()’: main.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type] 33 | } | ^
ソースコード
#include<cstdio>#include<queue>#include<utility>#include<cstring>#include<stack>#include<algorithm>#include<cmath>#include<iostream>#define MAX_N 100001#define INF 2147483647#define REP(i,n) for(int i=0;i<(int)(n);i++)void init(int n);int find(int n);void unite(int x,int y);bool same(int x, int y);int dx[4] = {1,0,0,-1};int dy[4] = {0,1,-1,0};using namespace std;struct edge{int from,to;};typedef vector<vector<edge> > AdjList;typedef long long ll;typedef pair<int , int> P;long long int MOD = 1000000007;long long int ruiseki[200001];int ncrset(){ruiseki[0] = 1;for(int i=1;i<200001;i++){ruiseki[i] = (ruiseki[i-1] * i) % MOD;}}long long int powld(long long int x,long long int n){long long int ans = 1;while(n > 0){if((n&1) == 1){ans = (ans*x) % MOD;}x = (x*x) % MOD;n >>= 1;}return ans % MOD;}ll ncrgyaku(ll n,ll r){long long int gyakuk,gyakur;long long int res = 1,x,y,z;y = powld(ruiseki[r],MOD-2);z = powld(ruiseki[n-r],MOD-2);return (((ruiseki[n]*y) % MOD)*z) % MOD;}vector< vector<ll> > graph[4];ll N,M,u,v;string S;ll memo[100001];ll solve(int n,int LEVEL){if(memo[n] != -1)return memo[n];if(LEVEL == 3){return memo[n] = 1;}LEVEL++;ll res=0;for(int i=0;i<graph[LEVEL][n].size();i++){res = (res+solve(graph[LEVEL][n][i],LEVEL))%MOD;}return memo[n] = res;}int main(){REP(i,100001){memo[i] = -1;}cin >> N >> M;cin >> S;REP(i,4)graph[i] = vector<vector<ll> >(N,vector<ll>(0));REP(i,M){cin >> u >> v;u--;v--;if(S[u] == 'P'){graph[0][v].push_back(u);}else if(S[u] == 'D'){graph[1][v].push_back(u);}else if(S[u] == 'C'){graph[2][v].push_back(u);}else{graph[3][v].push_back(u);}if(S[v] == 'P'){graph[0][u].push_back(v);}else if(S[v] == 'D'){graph[1][u].push_back(v);}else if(S[v] == 'C'){graph[2][u].push_back(v);}else{graph[3][u].push_back(v);}}ll res = 0;for(int i=0;i<S.size();i++){if(S[i] == 'P'){res = (res+ solve(i,0))%MOD;}}cout << res << endl;return 0;}int par[MAX_N];int ranks[MAX_N];//n要素で初期化void init(int n){REP(i,n){par[i] = i;ranks[i] = 0;}}//木の根を求めるint find(int x){if(par[x] == x){return x;}else{return par[x] = find(par[x]);}}void unite(int x,int y){x = find(x);y = find(y);if(x == y) return ;if(ranks[x] < ranks[y]){par[x] = y;}else{par[y] = x;if(ranks[x] == ranks[y]) ranks[x]++;}}bool same(int x, int y){return find(x) == find(y);}