| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 878822 |
2023-11-25T09:32:57 Z |
mosaev |
Tug of War (BOI15_tug) |
C++17 |
|
9 ms |
7512 KB |
#include <bits/stdc++.h>
#include <set>
//#include <multi_set>
#include <bitset>
using namespace std;
#define ll long long
#define N (ll)(3e4+5)
#define fi first
#define se second
ll n, k, ce, cv, d[2*N];
bool seen[2*N];
vector<pair<ll, ll>> v[2*N], tmp;
vector<ll> e;multiset<ll> st;
queue<ll> q;
bitset<(ll)(2e6)> bs;
void dfs(ll s){d[s] = v[s].size();seen[s] = true;cv++;ce += v[s].size();for(auto x:v[s]) if(!seen[x.fi]) dfs(x.fi);}
ll ddfs(ll s, ll p, ll z){seen[s] = true;if(p == 0){ce += v[s][0].se, ce -= v[s][1].se;ddfs(v[s][0].fi, s, z*(-1));}else{for(auto x:v[s]) if(!seen[x.fi]) ce += z*x.se, ddfs(x.fi, s, z*(-1));}}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;ll a, b, c;
for(int i=1; i<=2*n; i++) cin >> a >> b >> c, b += n, v[a].push_back({b, c}), v[b].push_back({a, c});
for(int i = 1; i<=2*n; i++) if(!seen[i]) {
cv = ce = 0;dfs(i);ce/=2;if(ce != cv) return cout << "NO", 0;
}
memset(seen, 0, sizeof(seen));
for(int i=1; i<=2*n; i++) if(d[i] == 1) q.push(i);
while(q.size()){
a = q.front();q.pop();
seen[a] = true;for(auto x:v[a]) {
d[x.fi]--;if(d[x.fi] == 1) q.push(x.fi);if(!seen[x.fi]) b = x.se;
}seen[a] = true;if(a > n) d[0]-=b;else d[0]+=b;
}
for(int i=1; i<=2*n; i++) {swap(tmp, v[i]), v[i].clear();for(auto x:tmp) if(!seen[x.fi]) v[i].push_back(x);if(seen[i]) v[i].clear();}
for(int i=1; i<=2*n; i++) if(!seen[i]) ce = 0, ddfs(i, 0, 1), st.insert(max(ce, -ce));
while(st.size()){
a = *st.begin();b = st.count(a);st.erase(a);e.push_back(a);b--;
while(b >= 2) b-=2, st.insert(a*2);if(b == 1) e.push_back(a);
}
bs[(ll)1e6 + d[0]] = 0b1;
for(auto x:e) bs = (bs>>x)|(bs<<x);
for(int i=0; i<(ll)1e6-2; i++) if(bs[(ll)1e6 + i] || bs[(ll)1e6 - i]) return cout << (i <= k ? "YES":"NO"), 0;
cout << "NO";
}
Compilation message
tug.cpp: In function 'long long int ddfs(long long int, long long int, long long int)':
tug.cpp:17:192: warning: no return statement in function returning non-void [-Wreturn-type]
17 | ll ddfs(ll s, ll p, ll z){seen[s] = true;if(p == 0){ce += v[s][0].se, ce -= v[s][1].se;ddfs(v[s][0].fi, s, z*(-1));}else{for(auto x:v[s]) if(!seen[x.fi]) ce += z*x.se, ddfs(x.fi, s, z*(-1));}}
| ^
tug.cpp: In function 'int main()':
tug.cpp:37:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
37 | while(b >= 2) b-=2, st.insert(a*2);if(b == 1) e.push_back(a);
| ^~~~~
tug.cpp:37:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
37 | while(b >= 2) b-=2, st.insert(a*2);if(b == 1) e.push_back(a);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
4956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
4956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
7512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
4956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
