結果
問題 | No.2673 A present from B |
ユーザー |
![]() |
提出日時 | 2024-02-12 19:26:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,791 bytes |
コンパイル時間 | 7,864 ms |
コンパイル使用メモリ | 458,140 KB |
実行使用メモリ | 99,356 KB |
最終ジャッジ日時 | 2024-09-29 23:21:26 |
合計ジャッジ時間 | 11,401 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | AC * 1 WA * 2 TLE * 1 -- * 20 |
ソースコード
/*このコード、と~おれ!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>#include <array>#include <chrono>#include <unordered_set>//#pragma GCC target("arch=skylake-avx512")//#pragma GCC target("avx2")//#pragma GCC optimize("O3")//#pragma GCC optimize("Ofast")//#pragma GCC target("sse4")//#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define repeat(i, n, m) for(int i = n; i < (m); ++i)#define rep(i, n) for(int i = 0; i < (n); ++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())#define all(x) (x).begin(), (x).end()#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))using ll = long long;using ull = unsigned long long;constexpr int INF = 1073741823;constexpr int MINF = -1073741823;constexpr ll LINF = ll(4661686018427387903);constexpr ll MOD = 1e9 + 7;constexpr ll mod = 998244353;constexpr long double eps = 1e-14;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>inline T chmin(T& a, const T& b) {if (a > b)a = b;return a;}template<typename T>inline T chmax(T& a, const T& b) {if (a < b)a = b;return a;}//cpp_int#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>#include <boost/multiprecision/cpp_dec_float.hpp>using namespace boost::multiprecision;#elseusing cpp_int = ll;#endif//atcoder library#if __has_include(<atcoder/all>)#include <atcoder/all>//using namespace atcoder;#endif/*random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution dist(1, 100);*//*----------------------------------------------------------------------------------*//** @title template(graph)* @docs kyopro/docs/graph_template.md*/template<typename T>struct edge {T cost;int from, to;edge(int from, int to) : from(from), to(to), cost(T(1)) {}edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}};template<typename T = int>struct graph {int n;bool directed, weighted;vector<vector<edge<T>>> g;graph(int n, bool directed, bool weighted) : g(n), n(n), directed(directed), weighted(weighted) {}void add_edge(int from, int to, T cost = T(1)) {g[from].emplace_back(from, to, cost);if (not directed) {g[to].emplace_back(to, from, cost);}}vector<edge<T>>& operator[](const int& idx) {return g[idx];}void read(int e, bool one_indexed) {int a, b, c = 1;while (e--) {scanf("%d%d", &a, &b);if (weighted) {scanf("%d", &c);}if (one_indexed)--a, --b;add_edge(a, b, c);}}void read(int e, bool one_indexed, const string& format) {int a, b;T c = T(1);while (e--) {scanf("%d%d", &a, &b);if (weighted) {scanf(format.c_str(), &c);}if (one_indexed)--a, --b;add_edge(a, b, c);}}};/** @title dijkstra* @docs kyopro/docs/dijkstra.md*/template<typename T = int>vector<T> dijkstra(graph<T>& g, const int& v, const int& n, const T Inf) {priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> priq;vector<T> res(n);fill(all(res), Inf);priq.push({ 0, v });res[v] = 0;int top;while (!priq.empty()) {top = priq.top().second;T cost = priq.top().first;priq.pop();if (cost > res[top])continue;for (const auto& aa : g[top]) {if (res[top] + aa.cost >= res[aa.to])continue;res[aa.to] = aa.cost + res[top];priq.push({ res[aa.to], aa.to });}}return res;}int main() {int n, m;scanf("%d%d", &n, &m);vector<int> a(m);rep(i, m) {scanf("%d", &a[i]);--a[i];}int cnt = 0;rep(i, m)if (a[i] == 1)++cnt;vector<int> p(n);rep(i, n)p[i] = i;vector<int> ans(n);rep(i, n)ans[i] = i + cnt;graph<int> g(n * (m + 1), true, true);rep(i, m) {g.add_edge(n * i + a[i], n * (i + 1) + a[i] + 1, 0);g.add_edge(n * i + a[i] + 1, n * (i + 1) + a[i], 0);rep(j, n) {if(a[i] != j and a[i] + 1 != j)g.add_edge(n * i + j, n * (i + 1) + j, 0);}rep(j, n - 1) {g.add_edge(n * i + j, n * i + j + 1, 1);g.add_edge(n * i + j + 1, n * i + j, 1);}}rep(i, n - 1) {g.add_edge(n * m + i, n * m + i + 1, 1);g.add_edge(n * m + i + 1, n * m + i, 1);}vector<vector<int>> dist(n);rep(i, n)dist[i] = dijkstra(g, i, n * (m + 1), INF);rep(i, n - 1)printf("%d\n", dist[i + 1][n * m]);Please AC;}