結果
| 問題 | No.654 Air E869120 |
| ユーザー |
 7deQSJCy8c4Hg7I
|
| 提出日時 | 2023-11-22 18:05:21 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 24,304 bytes |
| コンパイル時間 | 2,735 ms |
| コンパイル使用メモリ | 172,416 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-26 07:35:26 |
| 合計ジャッジ時間 | 3,767 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 1 ms
5,376 KB |
| testcase_05 | AC | 1 ms
5,376 KB |
| testcase_06 | AC | 1 ms
5,376 KB |
| testcase_07 | AC | 1 ms
5,376 KB |
| testcase_08 | AC | 1 ms
5,376 KB |
| testcase_09 | AC | 2 ms
5,376 KB |
| testcase_10 | AC | 3 ms
5,376 KB |
| testcase_11 | AC | 3 ms
5,376 KB |
| testcase_12 | AC | 3 ms
5,376 KB |
| testcase_13 | AC | 3 ms
5,376 KB |
| testcase_14 | AC | 3 ms
5,376 KB |
| testcase_15 | AC | 3 ms
5,376 KB |
| testcase_16 | AC | 3 ms
5,376 KB |
| testcase_17 | AC | 4 ms
5,376 KB |
| testcase_18 | AC | 4 ms
5,376 KB |
| testcase_19 | AC | 4 ms
5,376 KB |
| testcase_20 | AC | 3 ms
5,376 KB |
| testcase_21 | AC | 4 ms
5,376 KB |
| testcase_22 | AC | 4 ms
5,376 KB |
| testcase_23 | AC | 4 ms
5,376 KB |
| testcase_24 | AC | 4 ms
5,376 KB |
| testcase_25 | AC | 3 ms
5,376 KB |
| testcase_26 | AC | 4 ms
5,376 KB |
| testcase_27 | AC | 3 ms
5,376 KB |
| testcase_28 | AC | 4 ms
5,376 KB |
| testcase_29 | AC | 4 ms
5,376 KB |
| testcase_30 | AC | 3 ms
5,376 KB |
| testcase_31 | AC | 3 ms
5,376 KB |
| testcase_32 | AC | 3 ms
5,376 KB |
| testcase_33 | AC | 3 ms
5,376 KB |
| testcase_34 | AC | 3 ms
5,376 KB |
| testcase_35 | AC | 1 ms
5,376 KB |
| testcase_36 | AC | 1 ms
5,376 KB |
| testcase_37 | AC | 2 ms
5,376 KB |
| testcase_38 | AC | 2 ms
5,376 KB |
| testcase_39 | AC | 2 ms
5,376 KB |
コンパイルメッセージ
main.cpp:496:21: warning: | has lower precedence than >; > will be evaluated first [-Wparentheses]
496 | return (r.a > l.a | (r.a == l.a & r.b > l.b) |
| ~~~~~~~~~~^
main.cpp:496:21: note: place parentheses around the '>' expression to silence this warning
496 | return (r.a > l.a | (r.a == l.a & r.b > l.b) |
| ^
| ( )
main.cpp:496:21: note: place parentheses around the | expression to evaluate it first
496 | return (r.a > l.a | (r.a == l.a & r.b > l.b) |
| ^
| ( )
main.cpp:500:21: warning: | has lower precedence than <; < will be evaluated first [-Wparentheses]
500 | return (r.a < l.a | (r.a == l.a & r.b < l.b) |
| ~~~~~~~~~~^
main.cpp:500:21: note: place parentheses around the '<' expression to silence this warning
500 | return (r.a < l.a | (r.a == l.a & r.b < l.b) |
| ^
| ( )
main.cpp:500:21: note: place parentheses around the | expression to evaluate it first
500 | return (r.a < l.a | (r.a == l.a & r.b < l.b) |
| ^
| ( )
main.cpp:510:21: warning: | has lower precedence than >; > will be evaluated first [-Wparentheses]
510 | return (r.a > l.a | (r.a == l.a & r.b > l.b) |
| ~~~~~~~~~~^
main.cpp:510:21: note: place parentheses around the '>' expression to silence this warning
510 | return (r.a > l.a | (r.a == l.a & r.b > l.b) |
| ^
| ( )
main.cpp:510:21: note: place parentheses around the | expression to evaluate it first
510 | return (r.a > l.a | (r.a == l.a & r.b > l.b) |
| ^
| ( )
main.cpp:514:21: warning: | has lower precedence than <; < will be evaluated first [-Wparentheses]
514 | return (r.a < l.a | (r.a
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using lll = __int128_t;
using vs = vector<string>;
using pii = pair<long long, long long>;
const long double EPS = 1e-10;
const double INF = 1e18;
const long double PI = acos(-1.0L);
#define mp make_pair
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) n.begin(), n.end()
#define rALL(n) n.rbegin(), n.rend()
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT \
std::ios::sync_with_stdio(false); \
std::cin.tie(0);
template <class T>
inline T CHMAX(T &a, const T b) {
return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
return a = (a > b) ? b : a;
}
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <deque> // deque
#include <iostream> // cout, endl, cin
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <string> // string, to_string, stoi
#include <tuple> // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility> // pair, make_pair
#include <vector> // vector
using namespace std;
#include <type_traits>
#define LOOP(n) REPI($_, (n))
#define REPI(i, n) \
for (int i = 0, i##_length = static_cast<int>(n); i < i##_length; ++i)
#define REPF(i, l, r) \
for (std::common_type_t<decltype(l), decltype(r)> i = (l), i##_last = (r); \
i < i##_last; ++i)
#define REPIS(i, l, r, s) \
for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
i = (l), \
i##_last = (r); \
i < i##_last; i += (s))
#define REPR(i, n) for (auto i = (n); --i >= 0;)
#define REPB(i, l, r) \
for (std::common_type_t<decltype(l), decltype(r)> i = (r), i##_last = (l); \
--i >= i##_last;)
#define REPRS(i, l, r, s) \
for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
i = (l) + ((r) - (l)-1) / (s) * (s), \
i##_last = (l); \
i >= i##_last; (i -= (s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i, n) \
for (int i = 0, i##_last = static_cast<int>(n); i <= i##_last; ++i)
#define FORI(i, l, r) \
for (std::common_type_t<decltype(l), decltype(r)> i = (l), i##_last = (r); \
i <= i##_last; ++i)
#define FORIS(i, l, r, s) \
for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
i = (l), \
i##_last = (r); \
i <= i##_last; i += (s))
#define FORRO(i, n) for (auto i = (n); i >= 0; --i)
#define FORR(i, l, r) \
for (std::common_type_t<decltype(l), decltype(r)> i = (r), i##_last = (l); \
i >= i##_last; --i)
#define FORRS(i, l, r, s) \
for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
i = (l) + ((r) - (l)) / (s) * (s), \
i##_last = (l); \
i >= i##_last; i -= (s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0, v) for (const auto &e0 : (v))
#define ITRP1(e0, v) for (auto e0 : (v))
#define ITRR1(e0, v) for (auto &e0 : (v))
#define ITR2(e0, e1, v) for (const auto [e0, e1] : (v))
#define ITRP2(e0, e1, v) for (auto [e0, e1] : (v))
#define ITRR2(e0, e1, v) for (auto &[e0, e1] : (v))
#define ITR3(e0, e1, e2, v) for (const auto [e0, e1, e2] : (v))
#define ITRP3(e0, e1, e2, v) for (auto [e0, e1, e2] : (v))
#define ITRR3(e0, e1, e2, v) for (auto &[e0, e1, e2] : (v))
#define ITR4(e0, e1, e2, e3, v) for (const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0, e1, e2, e3, v) for (auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0, e1, e2, e3, v) for (auto &[e0, e1, e2, e3] : (v))
#define ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) \
$OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) \
$OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
template <class Type>
class WeightedUnionFind {
public:
WeightedUnionFind() = default;
/// @brief 重み付き Union-Find 木を構築します。
/// @param n 要素数
explicit WeightedUnionFind(size_t n)
: m_parentsOrSize(n, -1), m_diffWeights(n) {}
/// @brief 頂点 i の root のインデックスを返します。
/// @param i 調べる頂点のインデックス
/// @return 頂点 i の root のインデックス
int find(int i) {
if (m_parentsOrSize[i] < 0) {
return i;
}
const int root = find(m_parentsOrSize[i]);
m_diffWeights[i] += m_diffWeights[m_parentsOrSize[i]];
// 経路圧縮
return (m_parentsOrSize[i] = root);
}
/// @brief a のグループと b のグループを統合します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @param w (b の重み) - (a の重み)
/// a を含むグループと b を含むグループを併合し、b の重みは a と比べて w
/// 大きくなるようにする
void merge(int a, int b, Type w) {
w += weight(a);
w -= weight(b);
a = find(a);
b = find(b);
if (a != b) {
// union by size (小さいほうが子になる）
if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) {
std::swap(a, b);
w = -w;
}
m_parentsOrSize[a] += m_parentsOrSize[b];
m_parentsOrSize[b] = a;
m_diffWeights[b] = w;
}
}
/// @brief (b の重み) - (a の重み) を返します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @remark a と b が同じグループに属さない場合の結果は不定です。
/// @return (b の重み) - (a の重み)
///(b の重み) - (a の重み) を返す。a と b
/// が同じグループに属さない場合の結果は不定
Type diff(int a, int b) { return (weight(b) - weight(a)); }
/// @brief a と b が同じグループに属すかを返します。
/// @param a 一方のインデックス
/// @param b 他方のインデックス
/// @return a と b が同じグループに属す場合 true, それ以外の場合は false
/// a と b が同じグループに属すかを返す
bool connected(int a, int b) { return (find(a) == find(b)); }
/// @brief i が属するグループの要素数を返します。
/// @param i インデックス
/// @return i が属するグループの要素数
int size(int i) { return -m_parentsOrSize[find(i)]; }
private:
// m_parentsOrSize[i] は i の 親,
// ただし root の場合は (-1 * そのグループに属する要素数)
std::vector<int> m_parentsOrSize;
// 重み
std::vector<Type> m_diffWeights;
Type weight(int i) {
find(i); // 経路圧縮
return m_diffWeights[i];
}
};
__int128 parse(string &s) {
__int128 ret = 0;
for (int i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0';
return ret;
}
ll GCD(ll m, ll n) {
// ベースケース
if (n == 0) return m;
// 再帰呼び出し
return GCD(n, m % n);
}
ll minlong = 0;
long long Power(long long a, long long b, long long m) {
long long p = a, Answer = 1;
for (int i = 0; i < 63; i++) {
ll wari = (1LL << i);
if ((b / wari) % 2 == 1) {
Answer %= m;
Answer = (Answer * p) % m; // 「a の 2^i 乗」が掛けられるとき
}
p %= m;
p = (p * p) % m;
}
return Answer;
}
// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
return (a * Power(b, m - 2, m)) % m;
}
// nCr mod 998244353 を返す関数
long long nCk(ll n, ll r) {
const long long M = 998244353;
// 手順 1: 分子 a を求める
long long a = 1;
for (int i = 1; i <= n; i++) a = (a * i) % M;
// 手順 2: 分母 b を求める
long long b = 1;
for (int i = 1; i <= r; i++) b = (b * i) % M;
for (int i = 1; i <= n - r; i++) b = (b * i) % M;
// 手順 3: 答えを求める
return Division(a, b, M);
}
using Interval = pair<ll, ll>;
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
vb kaku(N, false);
vll cur(N, INF);
cur[K] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
Q.push(make_pair(cur[K], K));
while (!Q.empty()) {
ll pos = Q.top().second;
Q.pop();
if (kaku[pos]) continue;
kaku[pos] = true;
for (ll i = 0; i < G[pos].size(); i++) {
ll nex = G[pos][i].first;
ll cost = G[pos][i].second;
if (cur[nex] > cur[pos] + cost) {
cur[nex] = cur[pos] + cost;
Q.push(make_pair(cur[nex], nex));
}
}
}
return cur;
}
template <typename T>
void Print(vector<T> &A) {
rep(i, A.size()) { cout << A[i] << ' '; }
cout << endl;
}
template <typename xy>
class BIT {
public:
BIT() = default;
// 長さ size の数列で初期化
explicit BIT(size_t size) : m_bit(size + 1) {}
// 数列で初期化
explicit BIT(const std::vector<xy> &v) : BIT(v.size()) {
for (int i = 0; i < v.size(); ++i) {
add((i + 1), v[i]);
}
}
// 閉区間 [1, r] の合計を返す (1-based indexing)
xy sum(int r) const {
xy ret = 0;
for (; 0 < r; r -= (r & -r)) {
ret += m_bit[r];
}
return ret;
}
// 閉区間 [l, r] の合計を返す (1-based indexing)
xy sum(int l, int r) const { return (sum(r) - sum(l - 1)); }
// 数列の i 番目の要素を加算 (1-based indexing)
void add(int i, xy value) {
for (; i < m_bit.size(); i += (i & -i)) {
m_bit[i] += value;
}
}
private:
std::vector<xy> m_bit;
};
// Binary Indexed Tree (1.2 区間加算対応)
// 1-based indexing
template <typename x>
class BIT_RAQ {
public:
BIT_RAQ() = default;
explicit BIT_RAQ(size_t size) : m_bit0(size), m_bit1(size) {}
explicit BIT_RAQ(const std::vector<x> &v) : m_bit0(v), m_bit1(v.size()) {}
// 閉区間 [1, r] の合計を返す (1-based indexing)
x sum(int r) const { return (m_bit0.sum(r) + m_bit1.sum(r) * r); }
// 閉区間 [l, r] の合計を返す (1-based indexing)
x sum(int l, int r) const { return (sum(r) - sum(l - 1)); }
// 数列の i 番目の要素を加算 (1-based indexing)
void add(int i, x value) { m_bit0.add(i, value); }
// 閉区間 [l, r] の要素を加算 (1-based indexing)
void add(int l, int r, x value) {
x a = (-value * (l - 1)), b = (value * r);
m_bit0.add(l, a);
m_bit0.add((r + 1), b);
m_bit1.add(l, value);
m_bit1.add((r + 1), -value);
}
private:
BIT<x> m_bit0;
BIT<x> m_bit1;
};
vll BFS(vvll &G, ll &x) {
vll cut(G.size(), INF);
queue<ll> Q;
Q.push(x);
cut[x] = 0;
while (!Q.empty()) {
ll a = Q.front();
Q.pop();
rep(i, G[a].size()) {
if (cut[G[a][i]] > cut[a] + 1) {
cut[G[a][i]] = cut[a] + 1;
Q.push(G[a][i]);
}
}
}
return cut;
}
void Yes(bool b) {
if (b)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
vector<long long> yaku(long long n) {
vector<long long> ret;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end()); // 昇順に並べる
return ret;
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
double randouble() { return 1.0 * rand() / RAND_MAX; }
struct Mo {
int n;
vector<pair<int, int>> lr;
explicit Mo(int n) : n(n) {} // nの値の設定を行う。
void add(int l, int r) { /* [l, r) */
lr.push_back({l, r});
}
template <typename AL, typename AR, typename EL, typename ER, typename O>
void build(const AL &add_left, const AR &add_right, const EL &erase_left,
const ER &erase_right, const O &out) {
int q = (int)lr.size(); // lr.size()はクエリの数に等しい。
int bs = n / min<int>(n, sqrt(q)); // 事実上bs>0となるように設定、
// cout << bs << endl;
vector<int> ord(q);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int a, int b) {
int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
if (ablock != bblock) return ablock < bblock; //
return (ablock & 1) ? lr[a].second > lr[b].second
: lr[a].second < lr[b].second;
// 偶奇で昇順・降順を分けることによって計算量が定数倍高速化する。
});
int l = 0, r = 0;
for (auto idx : ord) {
// cout << idx << endl;
while (l > lr[idx].first) add_left(--l);
while (r < lr[idx].second) add_right(r++);
while (l < lr[idx].first) erase_left(l++);
while (r > lr[idx].second) erase_right(--r);
out(idx);
}
}
template <typename A, typename E, typename O>
void build(const A &add, const E &erase, const O &out) {
build(add, add, erase, erase, out);
}
};
struct TRI {
ll a;
ll b;
ll c;
};
bool operator>(const TRI &r, const TRI &l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRI &r, const TRI &l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
struct TR {
ll a;
ll b;
ll c;
ll d;
};
bool operator>(const TR &r, const TR &l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TR &r, const TR &l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
struct TR5 {
ll a;
ll b;
ll c;
ll d;
ll e;
};
bool operator>(const TR5 &r, const TR5 &l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TR5 &r, const TR5 &l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
// Sはdataを表している。
using S = ll;
// Fはlazy(遅延伝搬用)を表している
using F = ll;
// 区間取得をどのようにするかを定義する。RMQだったらmin(a,b)とかになる。
S op(S a, S b) { return a + b; };
// op(e,a)=op(a,e)=aとなるような単位元を定義する。RMQの場合はINFが安牌
S e() { return 0; }
// 親のlazyが子のdataに対してどの様に作用させるかを定義する。区間加算をする場合はただ足せば良い
S mapping(F f, S x) { return x + f; }
/*親のlazyが子のlazyに対してどの様に作用させるかを定義する。区間加算をする場合はただ足せば良い
ただ可変では無い場合fが後の操作である事を留意しておくと良い*/
F composition(F f, F g) { return f + g; }
// mapping(a,id)=aとなる様なidを設定すれば良い今回の区間加算の場合は0が適する。区間乗算の場合は1が適する
F id() { return 0; }
ll half = 499122177;
// 条件を満たす場合オイラーツアーを考えれば出来る。
// 重要なのは求める次数を満たす辺を構築すること
// G:グラフ,P:オイラーツアーで探索した際に通った辺の番号の配列,in,out:最初と最後に通った時刻
// U[辺の番号]={親,現在いる位置}正の値だったら終点、それ以外親を出力することで頂点で表した経路の復元が可能
// num=辺の番号を記録,cou=時刻を記録
// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = extGCD(b, a % b, y, x);
y -= a / b * x;
return d;
}
vll toposo(vvll &G) {
// 帰りがけでやりたい場合はstack、幅優先でやりたい場合はqueueで行う
stack<ll> Q;
ll n = G.size();
vll A(n, 0);
rep(i, n) {
rep(j, G[i].size()) { A[G[i][j]]++; }
}
vb han(n, false);
rep(i, n) {
if (A[i] == 0) {
Q.push(i);
han[i] = true;
}
}
vll B;
while (!Q.empty()) {
ll a = Q.top();
Q.pop();
B.push_back(a);
rep(i, G[a].size()) {
if (!han[G[a][i]]) {
A[G[a][i]]--;
if (A[G[a][i]] == 0) {
Q.push(G[a][i]);
han[G[a][i]] = true;
}
}
}
}
if (B.size() != n) {
vll C(n, -2);
return C;
}
return B;
}
#include <bits/stdc++.h>
// ax+bのようなグラフの最小値をクエリ一個あたりO(1)で算出することが出来る。
// 条件は２つ存在する。
// 1.追加される順に傾きは単調減少でなければならない(傾きに関してソートする必要性が生じる)
// 2.追加される順にxは単調増加でなければならない(クエリ先読み等のひと手間が必要になる可能性がある)
// ２つの条件が満たせない場合はこのサンプルを使うことが出来ない(クエリが２種類存在し、直線の追加とxを指定して最小値を求める動作を平行して行う場合等)
struct ConvexHullTrick {
std::deque<std::pair<long long, long long>> dq; // （傾き、切片）
void add(long long a, long long b) {
std::pair<long long, long long> p0 = std::make_pair(a, b);
while (dq.size() >= 2) {
int sz = dq.size();
std::pair<long long, long long> p1 = dq[sz - 1];
std::pair<long long, long long> p2 = dq[sz - 2];
if ((p0.second - p1.second) * (p0.first - p2.first) <
(p0.second - p2.second) * (p0.first - p1.first))
break; // 交点のx座標を比較
dq.pop_back();
}
dq.push_back(p0);
}
long long query(long long x) {
while (dq.size() >= 2) {
long long v1 = dq[0].first * x + dq[0].second;
long long v2 = dq[1].first * x + dq[1].second;
if (v1 <= v2) break;
dq.pop_front();
}
return dq[0].first * x + dq[0].second;
}
};
// if(a <= b + EPS) // a <= b
// if(a < b - EPS) // a < b
// if(abs(a - b) < EPS) // a == b
// 頂点 s から頂点 t までの最大フローの総流量を返す
struct Edge {
long long to, cap, rev;
};
class MaximumFlow {
public:
int size_ = 0;
int level[2000];
int iter[2000];
vector<Edge> G[2000];
// 頂点数 N の残余グラフを準備
void init(int N) {
size_ = N;
memset(G, {}, size_);
for (int i = 0; i <= size_; i++) G[i].clear();
memset(level, -1,N);
memset(iter, 0, N);
}
// 頂点 a から b に向かう、上限 c リットル／秒の辺を追加
void add_edge(int a, int b, long long c) {
int Current_Ga = G[a].size(); // 現時点での G[a] の要素数
int Current_Gb = G[b].size(); // 現時点での G[b] の要素数
G[a].push_back(Edge{b, c, Current_Gb});
G[b].push_back(Edge{a, 0, Current_Ga});
}
// 頂点 a から b に向かう、上限 c リットル／秒の辺と頂点 b から a
// に向かう、上限 c リットル／秒の辺を追加
void Uadd_edge(int a, int b, long long c) {
int Current_Ga = G[a].size(); // 現時点での G[a] の要素数
int Current_Gb = G[b].size(); // 現時点での G[b] の要素数
G[a].push_back(Edge{b, c, Current_Gb});
G[b].push_back(Edge{a, c, Current_Ga});
}
// sからの最短距離をBDSで計算する
void bfs(int s, int t) {
memset(level, -1, sizeof(level));
queue<int> que;
level[s] = 0;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < G[v].size(); i++) {
Edge &e = G[v][i];
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
if (e.to == t) goto H;
que.push(e.to);
}
}
}
H:;
}
// 深さ優先探索（F はスタートから pos に到達する過程での "
// 残余グラフの辺の容量 " の最小値） 返り値は流したフローの量（流せない場合は
// 0 を返す）
long long dfs(int pos, int goal, long long F) {
// ゴールに到着：フローを流せる！
if (pos == goal) return F;
// 探索する
for (int &i = iter[pos]; i < G[pos].size(); i++) {
Edge &e = G[pos][i];
if (e.cap > 0 && level[pos] < level[e.to]) {
long long d = dfs(e.to, goal, min(F, e.cap));
// フローを流せる場合、残余グラフの容量を flow だけ増減させる
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
// すべての辺を探索しても見つからなかった ･･･
return 0;
}
// 頂点 s から頂点 t までの最大フローの総流量を返す
long long max_flow(int s, int t) {
long long Total_Flow = 0;
while (true) {
bfs(s, t);
if (level[t] < 0) return Total_Flow;
memset(iter, 0, sizeof(iter));
long long f = 0;
while ((f = dfs(s, t, (long long)1e18)) > 0) Total_Flow += f;
}
}
};
int main() {
cout << fixed << setprecision(20);
ll N, M;
ll a = 0, b = 0;
ll c = 0;
ll p = 1;
string S, T;
ll H, W;
ll K;
ll t;
cin >> N >> M >> K;
vll A(M), B(M), C(M), D(M), E(M);
rep(i, M) cin >> A[i] >> B[i] >> C[i] >> D[i] >> E[i];
MaximumFlow Z;
Z.init(M + 2);
rep(i, M) {
if (A[i] == 1) Z.add_edge(0, i + 1, INF);
if (B[i] == N) Z.add_edge(i + 1, M + 1, E[i]);
}
vector<vector<TR5>> G(N);
rep(i, M) { G[A[i] - 1].push_back({C[i], D[i], B[i] - 1, E[i], i}); }
rep(i, N) sort(ALL(G[i]));
rep(i, N-1) {
rep(j, G[i].size() - 1) {
Z.add_edge(G[i][j].e + 1, G[i][j + 1].e + 1, INF);
}
rep(j, G[i].size()) {
ll a = G[i][j].c;
if (a != N) {
rep(k, G[a].size()) {
if (G[i][j].b + K <= G[a][k].a) {
Z.add_edge(G[i][j].e + 1, G[a][k].e + 1, G[i][j].d);
break;
}
}
}
}
}
cout << Z.max_flow(0, M + 1) << endl;
}