Submission #120068

#	Time	Username	Problem	Language	Result	Execution time	Memory
120068		E869120	Tug of War (BOI15_tug)	C++14	100 / 100	1986 ms	14468 KiB

tug

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
#pragma warning (disable: 4996)

bitset<1200001>F;

bool solve(int N, int K, vector<int>G) {
	F.set(0);
	for (int i = 0; i < G.size(); i++) {
		F |= (F << (G[i] * 2));
	}
	int sm = 0; for (int i = 0; i < G.size(); i++) sm += G[i];
	for (int i = sm - K; i <= sm + K; i++) {
		if (i >= 0 && i <= sm * 2 && F[i] == 1) return true;
	}
	return false;
}

set<pair<int, int>> G[60009];
int N, K, V1, V2, A[60009], B[60009], S[60009]; bool used[60009], colored[60009];
vector<pair<int, int>> X[60009];

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N * 2; i++) {
		scanf("%d%d%d", &A[i], &B[i], &S[i]);
		G[A[i]].insert(make_pair(B[i] + N, i));
		G[B[i] + N].insert(make_pair(A[i], i));
	}

	queue<int>Q;
	for (int i = 1; i <= 2 * N; i++) {
		if (G[i].size() == 1) Q.push(i);
	}
	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		auto itr = G[pos].begin();
		pair<int, int> E = (*itr);

		if (pos <= N) V1 += S[E.second];
		else V2 += S[E.second];

		used[E.second] = false; colored[pos] = true;
		G[pos].erase(make_pair(E.first, E.second));
		G[E.first].erase(make_pair(pos, E.second)); if (G[E.first].size() == 1) Q.push(E.first);
	}
	for (int i = 1; i <= 2 * N; i++) {
		if (colored[i] == false && G[i].size() == 0) {
			cout << "NO" << endl;
			return 0;
		}
	}
	for (int i = 1; i <= 2 * N; i++) {
		auto itr = G[i].begin();
		while (itr != G[i].end()) {
			X[i].push_back(*itr);
			itr++;
		}
	}

	vector<int>Z; Z.push_back(abs(V1 - V2));
	for (int i = 1; i <= 2 * N; i++) {
		if (colored[i] == true) continue;

		vector<int>E;
		if (X[i][0].first == X[i][1].first) {
			colored[i] = true; colored[X[i][0].first] = true;
			E.push_back(S[X[i][0].second]);
			E.push_back(S[X[i][1].second]);
		}
		else {
			int cx = i;
			while (true) {
				int nex = -1, cost = -1;
				for (int j = 0; j < X[cx].size(); j++) {
					if (colored[X[cx][j].first] == false) { nex = X[cx][j].first; cost = S[X[cx][j].second]; }
				}
				if (nex == -1) break;
				cx = nex; colored[cx] = true; E.push_back(cost);
			}
		}

		int pa = 0, pb = 0;
		for (int j = 0; j < E.size(); j++) { if (j % 2 == 0) pa += E[j]; else pb += E[j]; }
		Z.push_back(abs(pa - pb));
	}

	bool FinalAns = solve(N, K, Z);
	if (FinalAns == true) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Compilation message (stderr)

tug.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
tug.cpp: In function 'bool solve(int, int, std::vector<int>)':
tug.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~
tug.cpp:16:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int sm = 0; for (int i = 0; i < G.size(); i++) sm += G[i];
                              ~~^~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < X[cx].size(); j++) {
                     ~~^~~~~~~~~~~~~~
tug.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < E.size(); j++) { if (j % 2 == 0) pa += E[j]; else pb += E[j]; }
                   ~~^~~~~~~~~~
tug.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A[i], &B[i], &S[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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