Submission #294139

#TimeUsernameProblemLanguageResultExecution timeMemory
294139ant101Tug of War (BOI15_tug)C++14
Compilation error
0 ms0 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <iomanip> #include <fstream> #include <cmath> #include <vector> #include <set> #include <unordered_set> #include <unordered_map> #include <map> #include <stack> #include <queue> #include <assert.h> #include <limits> #include <cstdio> #include <complex> using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef string str; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; #define mp make_pair #define f first #define s second typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; typedef vector<str> vs; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<pd> vpd; #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define rall(x) (x).rbegin(), (x).rend() #define rsz resize #define ins insert #define ft front() #define bk back() #define pf push_front #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define trav(a,x) for (auto& a: x) const int MOD = 1e9+7; // 998244353; // = (119<<23)+1 const int MX = 4e3+5; const ll INF = 1e18; const ld PI = 4*atan((ld)1); const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; namespace io { void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int if (sz(s)) { setIn(s+".in"); setOut(s+".out"); } // for USACO } } using namespace io; namespace input { template<class T> void re(complex<T>& x); template<class T1, class T2> void re(pair<T1,T2>& p); template<class T> void re(vector<T>& a); template<class T, size_t SZ> void re(array<T,SZ>& a); template<class T> void re(T& x) { cin >> x; } void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); } template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); } template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); } template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); } template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); } } namespace output { template<class T1, class T2> void pr(const pair<T1,T2>& x); template<class T, size_t SZ> void pr(const array<T,SZ>& x); template<class T> void pr(const vector<T>& x); template<class T> void pr(const set<T>& x); template<class T1, class T2> void pr(const map<T1,T2>& x); template<class T> void pr(const T& x) { cout << x; } template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { pr(first); pr(rest...); } template<class T1, class T2> void pr(const pair<T1,T2>& x) { pr("{",x.f,", ",x.s,"}"); } template<class T> void prContain(const T& x) { pr("{"); bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool> pr("}"); } template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); } template<class T> void pr(const vector<T>& x) { prContain(x); } template<class T> void pr(const set<T>& x) { prContain(x); } template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); } void ps() { pr("\n"); } template<class Arg> void ps(const Arg& first) { pr(first); ps(); // no space at end of line } template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) { pr(first," "); ps(rest...); // print w/ spaces } } using namespace output; using namespace input; ll add(ll a, ll b) { a += b; if(a >= MOD) { a -= MOD; } return a; } ll sub(ll a, ll b) { a -= b; if(a < 0) { a += MOD; } return a; } ll mul(ll a, ll b) { return (a * b)%MOD; } void add_self(ll& a, ll b) { a = add(a, b); } void sub_self(ll& a, ll b) { a = sub(a, b); } void mul_self(ll& a, ll b) { a = mul(a, b); } ll N, K; pl buckets[MX]; set<ll> r1[MX]; set<ll> r2[MX]; pl pref[MX]; ll skill[MX]; pair<ll, ll> cr1[MX], cr2[MX]; ll vis[MX]; bitset<80010> dp; ll ind = 0; /* ll lone = *(r1[i].begin()); r1[i].clear(); r2[pref[lone].s].erase(lone); if (r2[pref[lone].s].size() == 1) { <#statements#> } */ int main() { setIO(); re(N, K); FOR (i, 1, 2*N+1) { re(pref[i].f, pref[i].s, skill[i]); r1[pref[i].f].insert(i); r2[pref[i].s].insert(i); } FOR (i, 1, N+1) { if (!sz(r1[i]) || !sz(r2[i])) { ps("NO"); return 0; } } queue<pl> q; FOR (i, 1, N+1) { if (sz(r1[i]) == 1) { q.push({1, i}); } if (sz(r2[i]) == 1) { q.push({2, i}); } } ll currdiff = 0; while (!q.empty()) { pl todel = q.front(); q.pop(); if (todel.f == 1) { ll lone = *(r1[todel.s].begin()); r1[todel.s].clear(); r2[pref[lone].s].erase(lone); currdiff+=skill[lone]; if (r2[pref[lone].s].size() == 1) { q.push({2, pref[lone].s}); } } else { ll lone = *(r2[todel.s].begin()); r2[todel.s].clear(); r1[pref[lone].f].erase(lone); currdiff-=skill[lone]; if (r1[pref[lone].f].size() == 1) { q.push({1, pref[lone].f}); } } } FOR (i, 1, N+1) { if (r1[i].size() == 2) { cr1[i] = {*r1[i].begin(), *(--r1[i].end())}; } if (r2[i].size() == 2) { cr2[i] = {*r2[i].begin(), *(--r2[i].end())}; } } FOR (i, 1, N+1) { if (!vis[i] && r1[i].size() == 2) { ll diff1 = skill[cr1[i].f]; ll curr = cr1[i].s; ll currarr = 1; while (curr != cr1[i].f) { if (currarr == 1) { diff1-=skill[curr]; ll innd = pref[curr].s; if (cr2[innd].f == curr) { curr = cr2[innd].s; } else { curr = cr2[innd].f; } currarr = 2; } else { diff1+=skill[curr]; ll innd = pref[curr].f; if (cr1[innd].f == curr) { curr = cr1[innd].s; } else { curr = cr1[innd].f; } currarr = 1; } } ll diff2 = skill[cr1[i].s]; curr = cr1[i].f; currarr = 1; while (curr != cr1[i].s) { if (currarr == 1) { diff2-=skill[curr]; ll innd = pref[curr].s; if (cr2[innd].f == curr) { curr = cr2[innd].s; } else { curr = cr2[innd].f; } vis[pref[curr].f] = true; currarr = 2; } else { diff2+=skill[curr]; ll innd = pref[curr].f; if (cr1[innd].f == curr) { curr = cr1[innd].s; } else { curr = cr1[innd].f; } // vis[innd] = true; currarr = 1; } } vis[i] = true; // cout << ind << " " << i << "\n"; buckets[ind++] = {diff1, diff2}; } } dp[currdiff+40000] = 1; for (ll i = 0; i<ind; i++) { // for (ll j = 0; j<80010; j++) { // if (dp[0][j] != 1) { // continue; // } // if (j+buckets[i].f < 0 || j+buckets[i].f > 80000) { // // } else { // dp[1][j+buckets[i].f] = 1; // } // if (j+buckets[i].s < 0 || j+buckets[i].s > 80000) { // // } else { // dp[1][j+buckets[i].s] = 1; // } // } // for (ll j = 0; j<80010; j++) { // dp[0][j] = dp[1][j]; // dp[1][j] = 0; // } bitset<80010> b1, b2; if (buckets[i].f < 0) { b1 = dp >> -buckets[i].f; } else { b1 = dp << buckets[i].f; } if (buckets[i].s < 0) { b2 = dp >> -buckets[i].s; } else { b2 = dp << buckets[i].s; } dp = b1 | b2; } ll best = 1e13; for (ll i = 0; i<80010; i++) { if (!dp[i]) { continue; } best = min(best, abs(i-40000)); } if (best <= K) { cout << "YES" << "\n"; } else { cout << "NO" << "\n"; } return 0; }

Compilation message (stderr)

tug.cpp:176:1: error: 'bitset' does not name a type
  176 | bitset<80010> dp;
      | ^~~~~~
tug.cpp: In function 'int main()':
tug.cpp:300:5: error: 'dp' was not declared in this scope; did you mean 'dy'?
  300 |     dp[currdiff+40000] = 1;
      |     ^~
      |     dy
tug.cpp:321:9: error: 'bitset' was not declared in this scope
  321 |         bitset<80010> b1, b2;
      |         ^~~~~~
tug.cpp:18:1: note: 'std::bitset' is defined in header '<bitset>'; did you forget to '#include <bitset>'?
   17 | #include <complex>
  +++ |+#include <bitset>
   18 | using namespace std;
tug.cpp:321:23: error: 'b1' was not declared in this scope; did you mean 'r1'?
  321 |         bitset<80010> b1, b2;
      |                       ^~
      |                       r1
tug.cpp:321:27: error: 'b2' was not declared in this scope; did you mean 'r2'?
  321 |         bitset<80010> b1, b2;
      |                           ^~
      |                           r2
tug.cpp: In function 'void io::setIn(std::string)':
tug.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
tug.cpp: In function 'void io::setOut(std::string)':
tug.cpp:68:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~