結果
問題 | No.1069 電柱 / Pole (Hard) |
ユーザー | null |
提出日時 | 2020-04-27 03:54:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,078 bytes |
コンパイル時間 | 3,360 ms |
コンパイル使用メモリ | 192,612 KB |
最終ジャッジ日時 | 2025-01-10 02:24:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 77 TLE * 2 |
コンパイルメッセージ
main.cpp: In function ‘void scans(std::string&)’: main.cpp:78:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 78 | scanf("%c", &c); | ~~~~~^~~~~~~~~~ main.cpp:79:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 79 | if (c == '\n')scanf("%c", &c); | ~~~~~^~~~~~~~~~ main.cpp:82:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 82 | scanf("%c", &c); | ~~~~~^~~~~~~~~~ main.cpp: In function ‘void scanc(char&)’: main.cpp:88:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 88 | scanf("%c", &c); | ~~~~~^~~~~~~~~~ main.cpp:91:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 91 | scanf("%c", &c); | ~~~~~^~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:133:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 133 | scanf("%d%d%d%d%d", &n, &m, &k, &x, &y); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:140:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 140 | scanf("%d%d", &p, &q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:144:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 144 | scanf("%d%d", &p, &q); |
ソースコード
/* このコード、と~おれ! Be accepted! ∧_∧ (。・ω・。)つ━☆・*。 ⊂ ノ ・゜+. しーJ °。+ *´¨) .· ´¸.·*´¨) ¸.·*¨) (¸.·´ (¸.·'* ☆ */ #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <vector> #include <numeric> #include <iostream> #include <random> #include <map> #include <unordered_map> #include <queue> #include <regex> #include <functional> #include <complex> #include <list> #include <cassert> #include <iomanip> #include <set> #include <stack> #include <bitset> /*多倍長整数/cpp_intで宣言 #include <boost/multiprecision/cpp_int.hpp> using namespace boost::multiprecision; */ //#pragma gcc target ("avx2") //#pragma gcc optimization ("o3") //#pragma gcc optimization ("unroll-loops") #define rep(i, n) for(int i = 0; i < (n); ++i) #define rep1(i, n) for(int i = 1; i <= (n); ++i) #define rep2(i, n) for(int i = 2; i < (n); ++i) #define repr(i, n) for(int i = n; i >= 0; --i) #define reprm(i, n) for(int i = n - 1; i >= 0; --i) #define printynl(a) printf(a ? "yes\n" : "no\n") #define printyn(a) printf(a ? "Yes\n" : "No\n") #define printYN(a) printf(a ? "YES\n" : "NO\n") #define printim(a) printf(a ? "possible\n" : "imposible\n") #define printdb(a) printf("%.50lf\n", a) //少数出力 #define printLdb(a) printf("%.50Lf\n", a) //少数出力 #define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ) #define prints(s) printf("%s\n", s.c_str()) //string出力 #define all(x) (x).begin(), (x).end() #define allsum(a, b, c) ((a + b) * c / 2LL) //等差数列の和、初項,末項,項数 #define pb push_back #define rpriq priq<int, vector<int>, greater<int>> #define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI) #define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L) #define Please return #define AC 0 #define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */ using ll = long long; constexpr int INF = 1073741823; constexpr int MINF = -1073741823; constexpr ll LINF = ll(4661686018427387903); constexpr ll MOD = 1000000007; const long double PI = acosl(-1.0L); using namespace std; void scans(string& str) { char c; str = ""; scanf("%c", &c); if (c == '\n')scanf("%c", &c); while (c != '\n' && c != -1 && c != ' ') { str += c; scanf("%c", &c); } } void scanc(char& str) { char c; scanf("%c", &c); if (c == -1)return; while (c == '\n') { scanf("%c", &c); } str = c; } double acot(double x) { return PI / 2 - atan(x); } ll LSB(ll n) { return (n & (-n)); } /*-----------------------------------------ここからコード-----------------------------------------*/ template<typename T> vector<T> dijkstra(const vector<vector<pair<int, T>>>& graph, vector<int>& path, const int& v, const int& g, const int& n, const T inf, const vector<vector<bool>>& deleted, set<int> r) { priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> priq; vector<T> res(n); vector<int> prev(n); fill(all(prev), -1); fill(all(res), inf); priq.push({ 0, v }); res[v] = 0; int top; while (!priq.empty()) { top = priq.top().second; priq.pop(); for (const auto& aa : graph[top]) { if (res[top] + aa.second >= res[aa.first] or deleted[top][aa.first] or r.find(aa.first) != r.end())continue; res[aa.first] = aa.second + res[top]; prev[aa.first] = top; priq.push({ res[aa.first], aa.first }); } } for (int i = g; i != -1; i = prev[i])path.push_back(i); reverse(all(path)); return res; } int main() { int n, m, k, x, y; scanf("%d%d%d%d%d", &n, &m, &k, &x, &y); --x; --y; vector<vector<pair<int, long double>>> graph(n); vector<pair<int, int>> xy(n); set<vector<int>> routememo; int p, q; rep(i, n) { scanf("%d%d", &p, &q); xy[i] = { p, q }; } rep(i, m) { scanf("%d%d", &p, &q); --p; --q; long double a = xy[p].first, b = xy[p].second, c = xy[q].first, d = xy[q].second; graph[p].push_back({ q, sqrt((c - a) * (c - a) + (d - b) * (d - b)) }); graph[q].push_back({ p, sqrt((c - a) * (c - a) + (d - b) * (d - b)) }); } vector<vector<int>> path(k); vector<long double> ans(k), res, anstmp; vector<vector<bool>> deleted(n, vector<bool>(n)); res = dijkstra<long double>(graph, path[0], x, y, n, numeric_limits<long double>::infinity(), deleted, {}); ans[0] = res[y]; anstmp = res; routememo.insert(path[0]); auto func = [](const tuple<long double, vector<int>, vector<long double>>& a, const tuple<long double, vector<int>, vector<long double>>& b) -> bool { if (get<0>(a) != get<0>(b))return get<0>(a) > get<0>(b); else if (get<1>(a) != get<1>(b))return get<1>(a) > get<1>(b); else return get<2>(a) > get<2>(b); }; priority_queue<tuple<long double, vector<int>, vector<long double>>, vector<tuple<long double, vector<int>, vector<long double>>>, decltype(func)> priq{ func }; map<vector<int>, vector<int>> spurnode; rep(i, k - 1) { int siz = path[i].size(); vector<int> route; set<int> r; long double cost = 0; rep(j, siz - 1) { route.push_back(path[i][j]); r.insert(path[i][j]); spurnode[route].push_back(path[i][j + 1]); if (j != 0) { for (const auto& aa : graph[path[i][j - 1]]) { if (aa.first == path[i][j]) { cost += aa.second; break; } } } for (const auto& aa : spurnode[route])deleted[path[i][j]][aa] = deleted[aa][path[i][j]] = true; if (j > 0)deleted[path[i][j - 1]][path[i][j]] = deleted[path[i][j]][path[i][j - 1]] = true; res = dijkstra<long double>(graph, path[i + 1], path[i][j], y, n, numeric_limits<long double>::infinity(), deleted, r); if (j > 0)deleted[path[i][j - 1]][path[i][j]] = deleted[path[i][j]][path[i][j - 1]] = false; for (const auto& aa : spurnode[route])deleted[path[i][j]][aa] = deleted[aa][path[i][j]] = false; if (res[y] == numeric_limits<long double>::infinity())continue; vector<int> tmp; vector<long double> tmp2(n); for (int l = 0; l <= j; ++l) { tmp2[path[i][l]] = anstmp[path[i][l]]; } int l = 0; for (; path[i][l] != path[i][j]; ++l) { tmp2[path[i][l]] = anstmp[path[i][l]]; tmp.push_back(path[i][l]); } for (l = 0; path[i + 1][l] != y; ++l) { tmp2[path[i + 1][l]] = res[path[i + 1][l]]; tmp.push_back(path[i + 1][l]); } tmp.push_back(y); int siz2 = path[i + 1].size(); for (int l = 1; l < siz2; ++l) tmp2[path[i + 1][l]] = res[path[i + 1][l]] + anstmp[path[i][j]]; priq.push(make_tuple(cost + res[y], tmp, tmp2)); } if (priq.empty()) { for (; i < k - 1; ++i)ans[i + 1] = -1; break; } auto tmp = priq.top(); priq.pop(); while (routememo.find(get<1>(tmp)) != routememo.end() and !priq.empty()) { tmp = priq.top(); priq.pop(); } if (routememo.find(get<1>(tmp)) != routememo.end() and priq.empty()) { for (; i < k - 1; ++i)ans[i + 1] = -1; break; } path[i + 1] = get<1>(tmp); ans[i + 1] = get<0>(tmp); routememo.insert(path[i + 1]); //anstmp = get<2>(tmp); } rep(i, k)printLdb(ans[i]); Please AC; }