#967634 (C++23) No.2712 Play more!

提出ソース

結果

問題	No.2712 Play more!
ユーザー	idat_50me
提出日時	2024-03-31 15:26:26
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	8,163 bytes
コンパイル時間	3,288 ms
コンパイル使用メモリ	265,880 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-03-31 18:05:34
合計ジャッジ時間	4,339 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	39 ms 6,676 KB
testcase_08	AC	4 ms 6,676 KB
testcase_09	AC	80 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	3 ms 6,676 KB
testcase_12	AC	4 ms 6,676 KB
testcase_13	AC	3 ms 6,676 KB
testcase_14	AC	4 ms 6,676 KB
testcase_15	AC	4 ms 6,676 KB
testcase_16	AC	3 ms 6,676 KB
testcase_17	AC	3 ms 6,676 KB
testcase_18	AC	3 ms 6,676 KB
testcase_19	AC	2 ms 6,676 KB
testcase_20	AC	3 ms 6,676 KB
testcase_21	AC	4 ms 6,676 KB
testcase_22	AC	3 ms 6,676 KB
testcase_23	AC	3 ms 6,676 KB
testcase_24	AC	3 ms 6,676 KB
testcase_25	AC	3 ms 6,676 KB
testcase_26	AC	2 ms 6,676 KB
testcase_27	AC	3 ms 6,676 KB
testcase_28	AC	13 ms 6,676 KB
testcase_29	AC	3 ms 6,676 KB
testcase_30	AC	3 ms 6,676 KB
testcase_31	AC	9 ms 6,676 KB
testcase_32	AC	9 ms 6,676 KB
testcase_33	AC	2 ms 6,676 KB
testcase_34	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

// -------------------- main code begins at #263 -------------------- //

#include <bits/stdc++.h>
using namespace std;

template<typename T, typename U> using vp = vector<pair<T, U>>;
template<typename T> using pque = priority_queue<T>;
template<typename T> using lpque = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename U> using umap = unordered_map<T, U>;
template<typename T> using uset = unordered_set<T>;
#define pque_op(T, op) (priority_queue<T, vector<T>, decltype(op)>(op))
#define set_op(T, op, ...) (set<T, decltype(op)>(__VA_OPT__(__VA_ARGS__, ) op))

using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
using pil = pair<int, lint>;
using pli = pair<lint, int>;
using vint = vector<int>;
using vlint = vector<lint>;
using vpint = vector<pint>;
using vplint = vector<plint>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vbl = vector<bool>;
using qint = queue<int>;
using qlint = queue<lint>;

constexpr double PI = 3.141592653589793;
constexpr int INTINF = (1 << 30) - 1;
constexpr lint LLINF = (1LL << 62) - 1;
constexpr int MPRIME = 1000000007;
constexpr int MPRIME9 = 998244353;
constexpr lint MMPRIME = (1LL << 61) - 1;
constexpr char newl = '\n';

#define len length()
#define empb(...) emplace_back(__VA_ARGS__)
#define fi first
#define se second

#define get_rep(_1, _2, _3, func, ...) func
#define rep(i, ...) get_rep(__VA_ARGS__, rep3, rep2, rep1)(i, __VA_ARGS__)
#define rep1(i, N) for(int i = 0; i < (N); i++)
#define rep2(i, s, t) for(int i = (s); i < (t); i++)
#define rep3(i, s, t, a) for(int i = (s); i < (t); i += (a))
#define get_rrep(_1, _2, _3, func, ...) func
#define rrep(i, ...) get_rrep(__VA_ARGS__, rrep3, rrep2, rrep1)(i, __VA_ARGS__)
#define rrep1(i, N) for(int i = (N); i >= 0; i--)
#define rrep2(i, s, t) for(int i = (s); i >= (t); i--)
#define rrep3(i, s, t, a) for(int i = (s); i >= (t); i -= (a))
#define forbit(bit, k) for(int bit = 0; bit < (1 << (k)); bit++)
#define forsubset(bit, orig_bit)                                                                        \
	for(int bit = (orig_bit), _cnt = 0; (_cnt += (bit == (orig_bit))) < 2; --bit &= (orig_bit))
#define bitpop(bit, k) (((bit) >> (k)) & 1)

#define all(name) name.begin(), name.end()
#define rall(name) name.rbegin(), name.rend()
#define gsort(vbeg, vend) sort(vbeg, vend, greater<>())

#define dbg(x) cerr << #x << ": " << x << '\n';

inline int popcnt(lint bit) {
	return __builtin_popcountll(bit);
}

template<class T> inline bool chmin(T &a, T b) {
	if(a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T &a, T b) {
	if(a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T> inline void init(vector<T> &v) {
	for(auto &a : v) cin >> a;
}
template<class T, class U> inline void init(vector<pair<T, U>> &v) {
	for(auto &a : v) cin >> a.first >> a.second;
}

template<class T> inline void init(vector<T> &v, int n) {
	v.resize(n);
	for(auto &a : v) cin >> a;
}
template<class T1, class T2> inline void init(vector<T1> &v1, vector<T2> &v2, int n) {
	v1.resize(n);
	v2.resize(n);
	for(int i = 0; i < n; i++) cin >> v1[i] >> v2[i];
}
template<class T1, class T2, class T3>
inline void init(vector<T1> &v1, vector<T2> &v2, vector<T3> &v3, int n) {
	v1.resize(n);
	v2.resize(n);
	v3.resize(n);
	for(int i = 0; i < n; i++) cin >> v1[i] >> v2[i] >> v3[i];
}
template<class T, class U> inline void init(vector<pair<T, U>> &v, int n) {
	v.resize(n);
	for(auto &a : v) cin >> a.first >> a.second;
}

template<class T> inline void init(vector<T> &v, int n, const T &c) {
	v.resize(n);
	for(auto &a : v) {
		cin >> a;
		a += c;
	}
}
template<class T1, class T2>
inline void init(vector<T1> &v1, vector<T2> &v2, int n, const T1 &c1, const T2 &c2) {
	v1.resize(n);
	v2.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> v1[i] >> v2[i];
		v1[i] += c1;
		v2[i] += c2;
	}
}
template<class T1, class T2, class T3>
inline void
init(vector<T1> &v1, vector<T2> &v2, vector<T3> &v3, int n, const T1 &c1, const T2 &c2, const T3 &c3) {
	v1.resize(n);
	v2.resize(n);
	v3.resize(n);
	for(int i = 0; i < n; i++) {
		cin >> v1[i] >> v2[i] >> v3[i];
		v1[i] += c1;
		v2[i] += c2;
		v3[i] += c3;
	}
}
template<class T, class U> inline void init(vector<pair<T, U>> &v, int n, T &c1, U &c2) {
	v.resize(n);
	for(auto &a : v) {
		cin >> a.first >> a.second;
		a.first += c1;
		a.second += c2;
	}
}

inline void out() {
	cout << newl;
}
template<class T> inline void out(T a) {
	cout << a << '\n';
}
template<class T, class... U> inline void out(T a, U... lst) {
	cout << a << " ";
	out(forward<U>(lst)...);
}
template<class T> inline void out(vector<T> &v) {
	for(int i = 0; i < v.size(); i++) cout << v[i] << (i == v.size() - 1 ? '\n' : ' ');
	cout << flush;
}

template<class N> void resiz(N n) {}
template<class N, class T, class... U> void resiz(N n, T &&hd, U &&...tl) {
	hd.resize(n);
	resiz(n, forward<U>(tl)...);
}

bool Yes(bool b = true) {
	cout << (b ? "Yes" : "No") << newl;
	return b;
}
bool YES(bool b = true) {
	cout << (b ? "YES" : "NO") << newl;
	return b;
}
bool No(bool b = true) {
	if(!b) return false;
	cout << "No" << newl;
	return true;
}
bool NO(bool b = true) {
	if(!b) return false;
	cout << "NO" << newl;
	return true;
}

template<typename T> struct v2d {
private:
	vector<vector<T>> m;

public:
	v2d() {}
	v2d(int h, int w) : m(h, vector<T>(w)) {}
	v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
	v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}

	void assign(int h, int w) {
		m.assign(h, vector<T>(w));
	}
	void assign(int h, int w, const T init) {
		m.assign(h, vector<T>(w, init));
	}

	inline int size() const {
		return m.size();
	}

	void in() {
		for(vector<T> &v : m)
			for(T &val : v) cin >> val;
	}
	void in(int h, int w) {
		m.resize(h, vector<T>(w));
		in();
	}

	void out() {
		int h = m.size();
		for(vector<T> &v : m) {
			int sz = v.size();
			for(int j = 0; j < sz; j++) {
				cout << v[j] << (j == sz - 1 ? '\n' : ' ');
			}
		}
		cout << flush;
	}

	inline vector<T> &operator[](int idx) {
		assert(0 <= idx && idx < int(m.size()));
		return m[idx];
	}

	bool rangeout(int x, int y) {
		if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
		return false;
	}
};

long long binpow(long long a, long long ex, long long p = MMPRIME) {
	long long res = 1;
	while(ex > 0) {
		if(ex & 1) (res *= a) %= p;
		ex >>= 1;
		(a *= a) %= p;
	}
	return res;
}

inline void init_e(v2d<int> &E, int n, int m, int c) {
	E.assign(n, 0);
	int u, v;
	for(int i = 0; i < m; i++) {
		cin >> u >> v;
		u += c;
		v += c;
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
}

// -------------------- main code -------------------- //


int N, M;
vlint A;
vint X, Y;
vlint C;

v2d<int> E;
v2d<lint> W;
vlint score;
vint rch;
int inf_flag = 0;

void input() {
	cin >> N >> M;
	init(A, N);
	init(X, Y, C, M, -1, -1, 0ll);
}

lint dfs1(int x) {
	if(x == N - 1) {
		score[x] = A[N - 1];
		return score[x];
	}

	if(rch[x]) return score[x];
	rch[x] = 1;

	lint tscore = -LLINF;
	for(int i = 0; i < E[x].size(); i++) {
		int nx = E[x][i];
		lint nw = W[x][i];

		lint psc = dfs1(nx);
		if(psc == -LLINF) continue;
		chmax(score[x], psc - nw + A[x]);
	}
	return score[x];
}

void dfs2(int x, int orig, lint sc = 0, int flag = 0) {
	if(inf_flag) return;

	if(x == orig) {
		if(flag) {
			if(sc > 0) {
				inf_flag = 1;
				return;
			}
		}
		else {
			flag = 1;
		}
	}

	if(rch[x]) return;
	rch[x] = 1;

	for(int i = 0; i < E[x].size(); i++) {
		int nx = E[x][i];
		lint nw = W[x][i];

		dfs2(nx, orig, sc + A[x] + nw, flag);
	}
}

void solve() {
	E.assign(N, 0);
	W.assign(N, 0);
	for(int i = 0; i < M; i++) {
		E[X[i]].empb(Y[i]);
		W[X[i]].empb(C[i]);
	}

	score.assign(N, -LLINF);
	rch.assign(N, 0);
	dfs1(0);

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) rch[j] = 0;
		if(score[i] != -LLINF) {
			dfs2(i, i);
			if(inf_flag) {
				out("inf");
				return;
			}
		}
	}

	out(score[0]);
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while(t--) {
		input();
		solve();
	}
}

yukicoder

結果

テストケース

ソースコード