結果
問題 | No.92 逃走経路 |
ユーザー | Komaki__ |
提出日時 | 2014-12-07 19:24:13 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 31 ms / 5,000 ms |
コード長 | 4,552 bytes |
コンパイル時間 | 1,446 ms |
コンパイル使用メモリ | 157,644 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-02 09:20:36 |
合計ジャッジ時間 | 2,676 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 14 ms
4,380 KB |
testcase_06 | AC | 4 ms
4,380 KB |
testcase_07 | AC | 4 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 8 ms
4,380 KB |
testcase_10 | AC | 31 ms
4,380 KB |
testcase_11 | AC | 29 ms
4,376 KB |
testcase_12 | AC | 30 ms
4,376 KB |
testcase_13 | AC | 5 ms
4,380 KB |
testcase_14 | AC | 12 ms
4,376 KB |
testcase_15 | AC | 16 ms
4,380 KB |
testcase_16 | AC | 12 ms
4,380 KB |
testcase_17 | AC | 12 ms
4,376 KB |
testcase_18 | AC | 8 ms
4,380 KB |
testcase_19 | AC | 6 ms
4,380 KB |
ソースコード
#ifdef KOMAKI_LOCAL #include <omp.h> #else #define NDEBUG #endif #include <bits/stdc++.h> #include <sys/time.h> #include <unistd.h> using namespace std; #define i64 int64_t #define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i) #define sz(v) ((i64)((v).size())) #define bit(n) (((i64)1)<<((i64)(n))) #define all(v) (v).begin(), (v).end() template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){} template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); } template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; } #define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; } #define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; } #define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; } #define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; } #define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; } #define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; } #define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; } int main() { i64 n, m, k; cin >> n >> m >> k; vector<vector<tuple<i64, i64>>> edges(n); rep(i, m){ i64 a, b, c; cin >> a >> b >> c; --a; --b; edges[a].push_back(make_tuple(b, c)); edges[b].push_back(make_tuple(a, c)); } set<i64> cur; rep(i, n) cur.insert(i); rep(q, k){ i64 cost; cin >> cost; set<i64> next; for(auto t: cur)for(auto tup: edges[t])if(get<1>(tup) == cost){ next.insert(get<0>(tup)); } cur = next; } cout << sz(cur) << endl; for(auto t: cur) cout << t + 1 << " "; cout << endl; }