AOJ Patrol
AOJ Patrol
無向オイラー路の判定をするだけなので、スタート地点とゴール地点の字数が奇数でかつ他の点の字数がすべて偶数であるかどうかを判定するだけである。入力の受け取り方の方が面倒な問題......。
問題解いてる部分はここだけ。
bool f = true; rep(i, 110) if (i != 0 && i != 1 && sz(g[i]) & 1) f = false; puts((sz(g[0]) & 1) && (sz(g[1]) & 1) && f ? "OK" : "NG");
一応コードも。
#include "bits/stdc++.h" using namespace std; #define OUT(x) cout << #x << " = " << x << endl; #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) #define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++) #define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++) #define each(i, v) for (auto i : v) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb(x) push_back(x) #define bp(x) __builtin_popcount(x) #define mp(x, y) make_pair((x), (y)) #define fi first #define se second #define setp(x) setprecision(x) #define mset(m, v) memset(m, v, sizeof(m)) #define sz(x) (int)(x.size()) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; static const int MOD = 1000000007; static const double PI = 3.14159265358979; //#define int long long typedef vector<double> vd; typedef vector<string> vs; typedef vector<bool> vb; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pii> vpii; template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; } template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; } int in() { int _x; cin >> _x; return _x; } vi aa, bb; signed main() { int a, b; while (cin >> a >> b) { aa.pb(a); bb.pb(b); } int ap = 0; int bp = 0; while (true) { vi g[110]; while (aa[ap] != 0 && bb[bp] != 0) { int a, b; a = aa[ap]; b = bb[bp]; ap ++; bp ++; a --; b --; g[a].pb(b); g[b].pb(a); } ap ++; bp ++; bool f = true; rep(i, 110) if (i != 0 && i != 1 && sz(g[i]) & 1) f = false; puts((sz(g[0]) & 1) && (sz(g[1]) & 1) && f ? "OK" : "NG"); if (ap == sz(aa)) return 0; else continue; } }