#837237 (C++23) No.2202 贅沢てりたまチキン

提出ソース

結果

問題	No.2202 贅沢てりたまチキン
ユーザー	ゾビオ
提出日時	2023-02-03 22:22:44
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	177 ms / 2,000 ms
コード長	10,231 bytes
コンパイル時間	2,799 ms
コンパイル使用メモリ	252,832 KB
実行使用メモリ	27,196 KB
最終ジャッジ日時	2023-09-15 18:25:53
合計ジャッジ時間	5,811 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	6 ms 11,376 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	1 ms 4,376 KB
testcase_14	AC	141 ms 27,196 KB
testcase_15	AC	145 ms 27,192 KB
testcase_16	AC	105 ms 18,984 KB
testcase_17	AC	104 ms 18,988 KB
testcase_18	AC	52 ms 11,164 KB
testcase_19	AC	72 ms 17,372 KB
testcase_20	AC	137 ms 17,408 KB
testcase_21	AC	136 ms 17,468 KB
testcase_22	AC	83 ms 8,440 KB
testcase_23	AC	105 ms 8,424 KB
testcase_24	AC	95 ms 8,944 KB
testcase_25	AC	177 ms 18,188 KB
testcase_26	AC	140 ms 22,296 KB
testcase_27	AC	139 ms 22,376 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
//#include <atcoder/all> // AtCoder
using namespace std;
//using namespace atcoder; // AtCoder
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
//using mint = modint998244353; // AtCoder
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vvvll = vector<vector<vector<long long>>>;
using vvvvll = vector<vector<vector<vector<long long>>>>;
using dll = deque<long long>;
using ddll = deque<deque<long long>>;
using dddll = deque<deque<deque<long long>>>;
using ddddll = deque<deque<deque<deque<long long>>>>;
using pll = pair<long long, long long>;
using vpll = vector<pair<long long, long long>>;
using vvpll = vector<vector<pair<long long, long long>>>;
#define overload2(_1, _2, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for (ll i = 0; i < n; i++)
#define rep2(i, n) for (ll i = 0; i < n; i++)
#define rep3(i, a, b) for (ll i = a; i < b; i++)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define reps1(n) for (ll i = 1; i <= n; i++)
#define reps2(i, n) for (ll i = 1; i <= n; i++)
#define reps(...) overload2(__VA_ARGS__, reps2, reps1)(__VA_ARGS__)
#define rrep1(n) for (int i = n - 1; i >= 0; i--)
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)
#define rrep(...) overload4(__VA_ARGS__,rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rreps1(n) for (long long i = n; i >= 1; i--)
#define rreps2(i, n) for (long long i = n; i >= 1; i--)
#define rreps(...) overload2(__VA_ARGS__, rreps2, rreps1)(__VA_ARGS__)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define PI acos(-1.0)
#define YES printf("YES\n"), exit(0)
#define NO printf("NO\n"), exit(0)
#define Yes printf("Yes\n"), exit(0)
#define No printf("No\n"), exit(0)
#define MINUS printf("-1\n"), exit(0)
#define cuot cout // typo
#define endk endl //typo
constexpr char ln = '\n';
constexpr long long MOD = 998244353LL;
constexpr long long LINF = 0x1fffffffffffffff; // 4倍までOK 10^18より大きい
constexpr int INF = 0x3fffffff; // 2倍までOK 10^9より大きい
template<class T> void setcout(T n) {cout << setprecision(n) << fixed;}
template<class... T> constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<class... T> constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T> long long acc(const T& a){ return accumulate(all(a), 0LL); }
template<class T> long double accl(const T& a){ return accumulate(all(a), 0.0L); }
template<class T> vector<T> mrui(const vector<T>& a) { vector<T> ret(a.size() + 1); for(int i = 0; i < a.size(); i++) { ret[i + 1] = ret[i] + a[i]; } return ret; }
template <class T> vector<vector<T>> mrui2(const vector<vector<T>> &a) { vector<vector<T>> ret(a.size() + 1, vector<T>(a.front().size() + 1)); for(int i = 0; i < (int)a.size(); i++) { for(int j = 0; j < (int)a.front().size(); j++) { ret[i + 1][j + 1] = ret[i][j + 1] + ret[i + 1][j] - ret[i][j] + a[i][j]; } } return ret; }

inline void in(){}
template <class Head, class... Tail> inline void in(Head& head, Tail&... tail){ cin >> head; in(tail...); }

#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); in(name)
#define vv(type, name, h, ...) vector<vector<type>>name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, ...) vector<vector<type>>name(h, vector<type>(__VA_ARGS__)); in(name)
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>>name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p); // prototype

template <class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &p); // prototype

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v); // prototype

template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v); // prototype

template <class T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v); // prototype

template <class T>
istream &operator>>(istream &is, vector<T> &v); // prototype

template <class T, class S>
ostream &operator<<(ostream &os, const map<T, S> &mp); // prototype

template <class T>
ostream &operator<<(ostream &os, const set<T> &st); // prototype

template <class T>
ostream &operator<<(ostream &os, const multiset<T> &st); // prototype

template <class T>
ostream &operator<<(ostream &os, queue<T> q); // prototype

template <class T>
ostream &operator<<(ostream &os, deque<T> q); // prototype

template <class T>
ostream &operator<<(ostream &os, stack<T> st); // prototype

template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq); // prototype

//ostream &operator<<(ostream &os, const mint &i); //atcoder // prototype

//ostream &operator<<(ostream &os, const vector<mint> &v); //atcoder // prototype

//ostream &operator<<(ostream &os, const modint &i); //atcoder // prototype

//ostream &operator<<(ostream &os, const vector<modint> &v); //atcoder // prototype

template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
	is >> p.first >> p.second;
	return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i] << (i + 1 != (int)v.size() ? " " : "");
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i] << endl;
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {
	for (int i = 0; i < (int)v.size(); i++) {
		os << "i = " << i << endl;
		os << v[i];
	}
	return os;
}

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
	for (T &in : v) {
		is >> in;
	}
	return is;
}

template <class T, class S>
ostream &operator<<(ostream &os, const map<T, S> &mp) {
	for (auto &[key, val] : mp) {
		os << key << ": " << val << " ";
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const set<T> &st) {
	auto itr = st.begin();
	for (int i = 0; i < (int)st.size(); i++) {
		os << *itr << (i + 1 != (int)st.size() ? " " : "");
		itr++;
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, const multiset<T> &st) {
	auto itr = st.begin();
	for (int i = 0; i < (int)st.size(); i++) {
		os << *itr << (i + 1 != (int)st.size() ? " " : "");
		itr++;
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, queue<T> q) {
	while (q.size()) {
		os << q.front() << " ";
		q.pop();
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, deque<T> q) {
	while (q.size()) {
		os << q.front() << " ";
		q.pop_front();
	}
	return os;
}

template <class T>
ostream &operator<<(ostream &os, stack<T> st) {
	while (st.size()) {
		os << st.top() << " ";
		st.pop();
	}
	return os;
}

template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) {
	while (pq.size()) {
		os << pq.top() << " ";
		pq.pop();
	}
	return os;
}

/*ostream &operator<<(ostream &os, const mint &i) { //AtCoder
	os << i.val();
	return os;
}*/

/*ostream &operator<<(ostream &os, const vector<mint> &v) { //AtCoder
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i].val() << (i + 1 != (int)v.size() ? " " : "");
	}
	return os;
}*/

/*ostream &operator<<(ostream &os, const modint &i) { //AtCoder
	os << i.val();
	return os;
}*/

/*ostream &operator<<(ostream &os, const vector<modint> &v) { //AtCoder
	for (int i = 0; i < (int)v.size(); i++) {
		os << v[i].val() << (i + 1 != (int)v.size() ? "" : "");
	}
	return os;
}*/


//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

struct UnionFind {
	long long groups;
	vector<long long> parents;

	UnionFind(long long n) {
		groups = n;
		parents = vector<long long>(n, -1);
	}

	long long find(long long x) {
		if (parents.at(x) < 0) {
			return x;
		}else{
			parents[x] = find(parents[x]);
			return parents[x];
		}
	}

	void unite(long long x, long long y) {
		x = find(x);
		y = find(y);

		// already united
		if (x == y)
			return;

		groups--;

		if (parents[x] > parents[y])
			swap(x, y);

		parents[x] += parents[y];
		parents[y] = x;
	}

	long long size(long long x) {
		return -parents[find(x)];
	}

	bool issame(long long x, long long y) {
		return find(x) == find(y);
	}

	vector<long long> roots() {
		vector<long long> ret;
		for (long long i = 0; i < parents.size(); i++)
			if (parents[i] < 0)
				ret.push_back(i);
		return ret;
	}

	long long group_count() {
		return groups;
	}
};

int main() { //距離が奇数のパス
	ll n, m; cin >> n >> m;
	vvll g(n);
	UnionFind uf(n);
	rep(m) {
		ll a, b; cin >> a >> b; a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
		uf.unite(a, b);
	}
	vll d(n, -1);
	auto dfs = [&](auto&& self, ll cur, ll pre, ll c) -> bool { //奇数のサイクルを持つか
		if(d[cur] != -1) return c - d[cur] & 1;
		d[cur] = c;
		bool fl = false;
		for(auto nxt : g[cur]) {
			if(nxt != pre) fl |= self(self, nxt, cur, c + 1);
			if(fl) return true;
		}
		d[cur] = -1;
		return fl;
	};
	rep(i, n) {
		if(uf.find(i) != i) continue;
		if(!dfs(dfs, i, -1, 0)) No;
	}
	Yes;
}

yukicoder

結果

テストケース

ソースコード