結果

問題 No.1401 全自動マクロの作り方
ユーザー hotman78hotman78
提出日時 2021-02-19 19:13:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 3,153 ms
コード長 2,209 bytes
コンパイル時間 2,394 ms
コンパイル使用メモリ 207,784 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-14 14:25:08
合計ジャッジ時間 12,325 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 3 ms
4,352 KB
testcase_05 AC 3 ms
4,348 KB
testcase_06 AC 2 ms
4,352 KB
testcase_07 AC 3 ms
4,348 KB
testcase_08 AC 3 ms
4,352 KB
testcase_09 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "code.cpp"
//#include"testlib.h"
#include<bits/stdc++.h>
using namespace std;
using lint=long long;
#line 4 "cpplib/graph_tree/topological_sort.hpp"

/**
 * @brief トポロジカルソート
 */

std::vector<int>tsort(std::vector<std::vector<int>>G){
	std::vector<int> in(G.size(),0);
	std::vector<int> vis(G.size(),0);
	std::vector<int> res;
	for(int i=0;i<(int)G.size();i++)for(int j=0;j<(int)G[i].size();j++){
		in[G[i][j]]++;
	}
	for(int i=0;i<(int)G.size();++i){
		auto dfs=[&](auto dfs,int v)->void{
			vis[v]=1;
			res.push_back(v);
			for(auto e:G[v]){
				in[e]--;
				if(in[e]==0)dfs(dfs,e);
			}
		};
		if(vis[i]==0&&in[i]==0)dfs(dfs,i);
	}
	return res;
}
#line 6 "code.cpp"
const lint N_MIN=1,N_MAX=2000;
const lint D_MIN=1,D_MAX=2000;
const lint S_MIN=0,S_MAX=2000;

// int main(int argc, char** argv){
//     //registerValidation(argc, argv);
//     int n=inf.readInt(N_MIN,N_MAX);
//     inf.readEoln();
//     vector<vector<int>> g(2000);
//     int s=0;
//     vector<vector<int>>v(n);
//     for(int i=0;i<n;++i){
//         int d=inf.readInt(D_MIN,D_MAX);
//         s+=d;
//         v[i].resize(d);
//         for(int j=0;j<d;++j){
//             inf.readSpace();
//             v[i][j]=inf.readInt(S_MIN,S_MAX);
//         }
//         inf.readEoln();
//         if(v[i][0]!=v[i].back())g[v[i][0]].push_back(v[i].back());
//     }
//     inf.readEof();
//     assert(s<=2000);
//     for(int i=0;i<n;++i)for(int j=0;j<(int)v[i].size();++j){
//         assert(v[i][j]<s);
//     }
//     auto d=tsort(g);
//     if(d.size()!=2000){
//         cout<<0<<endl;
//     }else{
//         cout<<d.size()<<endl;
//         for(int i=0;i<(int)d.size();++i){
//             cout<<d[i]<<" "<<" \n"[i==d.size()-1];
//         }
//     }
// }

int main(){
    lint n;
    cin>>n;
    vector<vector<int>> g(2000);
    for(int i=0;i<n;++i){
        lint d;
        cin>>d;
        vector<int> v(d);
        for(int j=0;j<d;++j)cin>>v[j];
        if(v[0]!=v.back())g[v[0]].push_back(v.back());
    }
    auto d=tsort(g);
    if(d.size()!=2000){
        cout<<0<<endl;
    }else{
        cout<<d.size()<<endl;
        for(int i=0;i<(int)d.size();++i)cout<<d[i]<<" \n"[i==(int)d.size()-1];
    }
}
0