Submission #896307

#TimeUsernameProblemLanguageResultExecution timeMemory
896307arashMLGTug of War (BOI15_tug)C++17
100 / 100
1557 ms10844 KiB
#include<bits/stdc++.h> #ifdef LOCAL #include "Essentials/algo/debug.h" #else #define debug(...) 69 #endif #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int M = 3e4 + 23; const int N =M*2; const int LOG = 20; const int ZERO = N*LOG/2; const ll inf = 1e18; #define F first #define S second #define pb push_back #define kill(x) cout<<x<<endl, exit(0); #define all(x) x.begin(),x.end() #define sz(x) (int)x.size() #define lc (v << 1) #define rc ((v<<1) |1) int n,k; int w[N]; set<pii> G[N]; vector<int> vals; bitset<N*LOG> dp; int sum; void dfs(int v,int sex = 1) { if(sz(G[v])) { pii u = *G[v].begin(); G[v].clear(); G[u.F].erase({v,u.S}); sum += sex * w[u.S]; dfs(u.F,-sex); } } queue<int> Q; int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); cin>>n>>k; for(int i=0; i< 2*n ; i ++) { int l,r; cin>>l>>r>>w[i]; l--,r--; r += n; G[l].insert({r,i}); G[r].insert({l,i}); } for(int i = 0; i<2*n ; i ++) { if(!sz(G[i])) kill("NO"); if(sz(G[i]) == 1) { Q.push(i); } } int begsum = 0; while(sz(Q)) { int v = Q.front(); Q.pop(); pii u = *G[v].begin(); G[v].clear(); G[u.F].erase({v,u.S}); if(v < n) begsum += w[u.S]; else begsum -= w[u.S]; if(sz(G[u.F]) == 1) Q.push(u.F); } for(int i = 0; i < 2*n; i ++) if(sz(G[i])) { sum = 0; dfs(i); vals.pb(abs(sum)); } dp[ZERO+begsum] = 1; debug(vals); for(int val : vals) { dp = (dp << val) | (dp >> val); } for(int i = 0 ; i < N*LOG; i ++) if(dp[i] && abs(ZERO - i) <= k) kill("YES"); kill("NO"); return 0; } // Jumpsuit, Jumpsuit cover me! // Jumpsuit, Jumpsuit cover me!

Compilation message (stderr)

tug.cpp: In function 'int32_t main()':
tug.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
tug.cpp:79:2: note: in expansion of macro 'debug'
   79 |  debug(vals);
      |  ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...