結果
問題 | No.679 不思議マーケット |
ユーザー |
![]() |
提出日時 | 2018-04-27 23:26:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,291 bytes |
コンパイル時間 | 1,011 ms |
コンパイル使用メモリ | 105,024 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 22:20:06 |
合計ジャッジ時間 | 1,893 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#define _USE_MATH_DEFINES#pragma region include#include <iostream>#include <iomanip>#include <stdio.h>#include <sstream>#include <algorithm>#include <iterator>#include <cmath>#include <complex>#include <string>#include <cstring>#include <vector>#include <bitset>#include <queue>#include <set>#include <map>#include <stack>#include <list>#include <ctime>//////#include <random>//#pragma endregion //#include/////////#pragma region typedeftypedef long long LL;typedef long double LD;typedef unsigned long long ULL;#pragma endregion //typedef////定数const int INF = (int)1e9;const LL MOD = (LL)1e9+7;const LL LINF = (LL)4e18+20;const LD PI = acos(-1.0);const double EPS = 1e-9;/////////using namespace::std;vector<vector<int> > G,rG;vector<bool> visit;vector<int> dame;const int NG = -1;const int OK = 1;//買えない商品を設定//Gを使うvoid dfs(int v){if( dame[v] == NG ){return;}dame[v] = NG;int size = G[v].size();for(int i=0;i<size;++i){int next = G[v][i];dfs(next);}return;}//必要な商品をさかのぼる//rGを使うint Rdfs(int v){if( dame[v] == OK ){return OK;}if( visit[v] ){//ループdfs(v);return NG;}visit[v] = true;if( dame[v] == NG ){//買えない商品return NG;}int size = rG[v].size();for(int i=0;i<size;++i){int prev = rG[v][i];int res = Rdfs(prev);if( res == NG ){return res;}}dame[v] = OK;return OK;}void solve(){int N,M;/*N 商品M 条件が付いてる商品*/cin>> N >> M;G=vector<vector<int> >(N);rG=vector<vector<int> >(N);for(int i=0;i<M;++i){int g,r;cin>>g>>r;--g;//商品indexfor(int j=0;j<r;++j){int h;cin>>h;--h;G[h].push_back( g );rG[g].push_back( h );}}visit = vector<bool>(N,false);dame = vector<int>(N,0);for(int i=0;i<N;++i){if( visit[i] == false ){Rdfs(i);}}int ans = N;for(int i=0;i<N;++i){if( dame[i] == NG ){--ans;}}cout << ans << endl;}#pragma region mainsigned main(void){std::cin.tie(0);std::ios::sync_with_stdio(false);std::cout << std::fixed;//小数を10進数表示cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別solve();}#pragma endregion //main()