結果

問題 No.1401 全自動マクロの作り方
ユーザー hotman78hotman78
提出日時 2021-02-19 19:23:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 3,153 ms
コード長 1,672 bytes
コンパイル時間 8,575 ms
コンパイル使用メモリ 333,136 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 15:32:21
合計ジャッジ時間 16,769 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 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());
    }
    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];
        }
        cout<<flush;
    }
    inf.readEof();
}
0