Submission #1117872

#TimeUsernameProblemLanguageResultExecution timeMemory
1117872whatthemomooofun1729Tug of War (BOI15_tug)C++17
0 / 100
3050 ms5836 KiB
#include <iostream> #include <algorithm> #include <utility> #include <vector> #include <stack> #include <map> #include <queue> #include <set> #include <unordered_set> #include <unordered_map> #include <cstring> #include <cmath> #include <functional> #include <cassert> #include <iomanip> #include <numeric> #include <bitset> #include <sstream> #include <chrono> #include <random> #define ff first #define ss second #define PB push_back #define sz(x) int(x.size()) #define rsz resize #define fch(xxx, yyy) for (auto xxx : yyy) // abusive notation #define all(x) (x).begin(),(x).end() #define eps 1e-9 // more abusive notation (use at your own risk): // #define int ll using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vll = vector<ll>; // debugging void __print(int x) {std::cerr << x;} void __print(ll x) {std::cerr << x;} /* remember to uncomment this when not using THE MACRO */ void __print(unsigned x) {std::cerr << x;} void __print(ull x) {std::cerr << x;} void __print(float x) {std::cerr << x;} void __print(double x) {std::cerr << x;} void __print(ld x) {std::cerr << x;} void __print(char x) {std::cerr << '\'' << x << '\'';} void __print(const char *x) {std::cerr << '\"' << x << '\"';} void __print(const string& x) {std::cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {std::cerr << '{'; __print(x.ff); std::cerr << ", "; __print(x.ss); std::cerr << '}';} template<typename T> void __print(const T& x) {int f = 0; std::cerr << '{'; for (auto &i: x) std::cerr << (f++ ? ", " : ""), __print(i); std::cerr << "}";} void _print() {std::cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...);} void println() {std::cerr << ">--------------------<" << endl;} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // templates template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;} template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;} template <class T> using gr = greater<T>; template <class T> using vc = vector<T>; template <class T> using p_q = priority_queue<T>; template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>; template <class T1, class T2> using pr = pair<T1, T2>; mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count()); int rng(int M) {return (int)(rng_ll()%M);} /*returns any random number in [0, M) */ // const variables constexpr int INF = (int)2e9; constexpr int MOD = 998244353; constexpr long double EPS = (ld)1e-10, PI = 3.1415926535; constexpr ll LL_INF = (ll)3e18; constexpr int mod = (int)1e9 + 7; constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7 void setIO(const string& str) {// fast input/output ios_base::sync_with_stdio(false); cin.tie(nullptr); if (str.empty()) return; freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } const int MAXN = int(3e4) + 5; const int MAXK = int(40 * MAXN) + 5; int N, K; vc<pii> adj[MAXN * 2]; map<pii, vi> mp; int deg[MAXN * 2], cc[MAXN * 2], edges[MAXN * 2], siz[MAXN * 2]; pii parent[MAXN * 2]; bitset<MAXK> dp[2]; // DP values: use the index trick vi d; vc<pii> v; int sum = 0; int cycle_end, cycle_start, final_edge; int solve() { int D = sz(d); dp[0][d[0] + 20 * N] = dp[0][-d[0] + 20 * N] = true; // base cases for (int i = 1; i < D; ++i) { for (int j = 0; j <= 40 * N; ++j) { dp[1][j] = (j - d[i] >= 0 && dp[0][j - d[i]]) || (j + d[i] <= 40 * N && dp[0][j + d[i]]); // is the same as automatically resetting all of the bit values // transitions } swap(dp[1], dp[0]); } for (int i = 0; i <= 40 * N; ++i) { int sba = i - 20 * N; if (dp[0][i] && abs(sba + sum) <= K) { // testing to see if a solution exists return 1; } } return 0; } void dfs1(int u) { fch(to, adj[u]) { if (cc[to.ff] != -1) continue; cc[to.ff] = cc[u]; siz[cc[u]]++; dfs1(to.ff); } } void conn_comp() { for (int i = 1; i <= 2 * N; ++i) { cc[i] = -1; } for (int i = 1; i <= 2 * N; ++i) { if (cc[i] == -1) { cc[i] = i; siz[i] = 1; dfs1(i); } } } bool dfs(int u, int par) { //debug(u, par); deg[u] = 0; fch(to, adj[u]) { if (to.ff == par) continue; // skipping edge to parent vertex if (deg[to.ff] == 0) { cycle_end = u; cycle_start = to.ff; final_edge = to.ss; return true; } parent[to.ff] = {u, to.ss}; if (dfs(to.ff, parent[to.ff].ff)) return true; } return false; } signed main() { // TIME YOURSELF !!! setIO(""); cin >> N >> K; for (int i = 0; i < 2 * N; ++i) { int l, r, s; cin >> l >> r >> s; r += N; adj[l].PB({r, s}); adj[r].PB({l, s}); mp[{l, r}].PB(s); deg[l]++, deg[r]++; v.PB({l, r}); parent[i+1] = {-1, -1}; // just setting all of the values in parent[i] to -1 } conn_comp(); for (int i = 0; i < sz(v); ++i) { edges[cc[v[i].ff]]++; } for (int i = 1; i <= 2 * N; ++i) { if (edges[cc[i]] < siz[cc[i]]) { cout << "NO"; return 0; } } for (auto i = mp.begin(); i != mp.end(); i++) { if (sz(i->ss) == 2) { int A = (i->ss)[0], B = (i->ss)[1]; d.PB(abs(-A + B)); deg[(i->ff).ff] = deg[(i->ff).ss] = 0; } } queue<int> q; for (int i = 1; i <= 2 * N; ++i) { if (sz(adj[i]) == 1) { q.push(i); deg[i] = 1; } } while (!q.empty()) { int u = q.front(); q.pop(); fch(to, adj[u]) { sum += (u <= N ? -1 : 1) * to.ss; deg[to.ff]--; if (deg[to.ff] == 1) q.push(to.ff); } } for (int i = 1; i <= 2 * N; ++i) { if (deg[i] == 2) { int S = 0, bit = 0; deg[i] = 0; dfs(i, parent[i].ff); for (int u = cycle_end; u != cycle_start; u = parent[u].ff, bit ^= 1) { S += (bit == 0 ? -1 : 1) * parent[u].ss; if (u == cycle_start) break; } S += (bit == 0 ? -1 : 1) * final_edge; d.PB(abs(S)); } } cout << (solve() == 1 ? "YES" : "NO"); return 0; } // TLE -> TRY NOT USING DEFINE INT LONG LONG // CE -> CHECK LINE 45 // 5000 * 5000 size matrices are kinda big (potential mle) // Do something, start simpler

Compilation message (stderr)

tug.cpp: In function 'void setIO(const string&)':
tug.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tug.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...