Submission #878822

#	Time	Username	Problem	Language	Result	Execution time	Memory
878822		mosaev	Tug of War (BOI15_tug)	C++17	0 / 100	9 ms	7512 KiB

tug

#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 (stderr)

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);
      |                                      ^~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29