oj.uz

답안 #120055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120055 2019-06-23T07:05:46 Z E869120 Tug of War (BOI15_tug) C++14
0 / 100
 222 ms 31804 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#pragma warning (disable: 4996)

bool dp[2009][80009];

bool solve(int N, int K, vector<pair<int, int>>G) {
	dp[0][40000] = true;
	for (int i = 0; i < G.size(); i++) {
		for (int j = 0; j <= 80000; j++) {
			if (dp[i][j] == false) continue;
			dp[i + 1][j + G[i].first] = true;
			dp[i + 1][j + G[i].second] = true;
		}
	}
	for (int i = 40000 - K; i <= 40000 + K; i++) {
		if (dp[G.size()][i] == true) 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 += E.second;
		else V2 += 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<pair<int, int>>Z; Z.push_back(make_pair(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(make_pair(pa - pb, pb - pa));
	}

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

Compilation message

tug.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
tug.cpp: In function 'bool solve(int, int, std::vector<std::pair<int, int> >)':
tug.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G.size(); i++) {
                  ~~^~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:81:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < X[cx].size(); j++) {
                     ~~^~~~~~~~~~~~~~
tug.cpp:90: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:30: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:32: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
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4608 KB Output is correct
2 Correct 7 ms 4608 KB Output is correct
3 Correct 7 ms 4608 KB Output is correct
4 Correct 7 ms 4608 KB Output is correct
5 Correct 7 ms 4608 KB Output is correct
6 Correct 6 ms 4608 KB Output is correct
7 Correct 8 ms 4608 KB Output is correct
8 Correct 7 ms 4608 KB Output is correct
9 Correct 6 ms 4608 KB Output is correct
10 Correct 6 ms 4608 KB Output is correct
11 Correct 7 ms 4608 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 7 ms 4608 KB Output is correct
14 Correct 7 ms 4608 KB Output is correct
15 Correct 7 ms 4608 KB Output is correct
16 Correct 7 ms 4608 KB Output is correct
17 Correct 6 ms 4608 KB Output is correct
18 Correct 8 ms 4608 KB Output is correct
19 Correct 7 ms 4644 KB Output is correct
20 Correct 7 ms 4608 KB Output is correct
21 Correct 6 ms 4608 KB Output is correct
22 Correct 6 ms 4608 KB Output is correct
23 Incorrect 7 ms 4608 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4608 KB Output is correct
2 Correct 7 ms 4608 KB Output is correct
3 Correct 7 ms 4608 KB Output is correct
4 Correct 7 ms 4608 KB Output is correct
5 Correct 7 ms 4608 KB Output is correct
6 Correct 6 ms 4608 KB Output is correct
7 Correct 8 ms 4608 KB Output is correct
8 Correct 7 ms 4608 KB Output is correct
9 Correct 6 ms 4608 KB Output is correct
10 Correct 6 ms 4608 KB Output is correct
11 Correct 7 ms 4608 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 7 ms 4608 KB Output is correct
14 Correct 7 ms 4608 KB Output is correct
15 Correct 7 ms 4608 KB Output is correct
16 Correct 7 ms 4608 KB Output is correct
17 Correct 6 ms 4608 KB Output is correct
18 Correct 8 ms 4608 KB Output is correct
19 Correct 7 ms 4644 KB Output is correct
20 Correct 7 ms 4608 KB Output is correct
21 Correct 6 ms 4608 KB Output is correct
22 Correct 6 ms 4608 KB Output is correct
23 Incorrect 7 ms 4608 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 222 ms 31804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4608 KB Output is correct
2 Correct 7 ms 4608 KB Output is correct
3 Correct 7 ms 4608 KB Output is correct
4 Correct 7 ms 4608 KB Output is correct
5 Correct 7 ms 4608 KB Output is correct
6 Correct 6 ms 4608 KB Output is correct
7 Correct 8 ms 4608 KB Output is correct
8 Correct 7 ms 4608 KB Output is correct
9 Correct 6 ms 4608 KB Output is correct
10 Correct 6 ms 4608 KB Output is correct
11 Correct 7 ms 4608 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 7 ms 4608 KB Output is correct
14 Correct 7 ms 4608 KB Output is correct
15 Correct 7 ms 4608 KB Output is correct
16 Correct 7 ms 4608 KB Output is correct
17 Correct 6 ms 4608 KB Output is correct
18 Correct 8 ms 4608 KB Output is correct
19 Correct 7 ms 4644 KB Output is correct
20 Correct 7 ms 4608 KB Output is correct
21 Correct 6 ms 4608 KB Output is correct
22 Correct 6 ms 4608 KB Output is correct
23 Incorrect 7 ms 4608 KB Output isn't correct
24 Halted 0 ms 0 KB -