Submission #25194

#	Time	Username	Problem	Language	Result	Execution time	Memory
25194		minimario	Tug of War (BOI15_tug)	C++14	100 / 100	296 ms	27440 KiB

tug

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 30005;
 
set<int> left1[MAX];
set<int> right1[MAX];
int l[2*MAX], r[2*MAX], s[2*MAX]; // the people
 
int leftpts = 0;
int rightpts = 0;
int ropel[MAX], roper[MAX];
 
void nosolution() {
	printf("NO\n"); exit(0);
}
int main() {
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	int n, k; scanf("%d %d", &n, &k);
	set<int> students;
	for (int i=1; i<=2*n; i++) {
		scanf("%d %d %d", &l[i], &r[i], &s[i]);
		right1[r[i]].insert(i);
		left1[l[i]].insert(i);
		students.insert(i);
	}
	set<pair<int, int>> left_data, right_data;
 
	for (int i=1; i<=n; i++) {
		if (left1[i].empty() || right1[i].empty()) {
			nosolution();
		}
		left_data.insert({left1[i].size(), i});
		right_data.insert({right1[i].size(), i});
	}
 
	bool repeat = true;
	while (repeat) {
		repeat = false;
		if (!left_data.empty() && left_data.begin()->first <= 0) {
			nosolution();
		}
		if (!left_data.empty() && left_data.begin()->first == 1) {
			pair<int, int> fixed = *left_data.begin();
			int pos = fixed.second;
			int student = *(left1[pos].begin());
			leftpts += s[student];
			left_data.erase(fixed);
			left1[pos].erase(student);
			students.erase(student);
			ropel[pos] = student; // assign the student to the position on the rope
			int rightpos = r[student];
			right_data.erase({right1[rightpos].size(), rightpos});
			right1[rightpos].erase(student);
			right_data.insert({right1[rightpos].size(), rightpos});
			repeat = true;
		}
		if (!right_data.empty() && right_data.begin()->first <= 0) {
			nosolution();
		}
		if (!right_data.empty() && right_data.begin()->first == 1) {
			pair<int, int> fixed = *right_data.begin();
			int pos = fixed.second;
			int student = *right1[pos].begin();
			rightpts += s[student];
			right_data.erase(fixed);
			right1[pos].erase(student);
			students.erase(student);
			roper[pos] = student; // assign the student to the position on the rope
			int leftpos = l[student];
			left_data.erase({left1[leftpos].size(), leftpos});
			left1[leftpos].erase(student);
			left_data.insert({left1[leftpos].size(), leftpos});
			repeat = true;
		}
	}
	// for (int i : students) { cout << i << " "; } 
	set<int> lefts; // the collection of left values
	set<int> rights;
	vector<pair<int, int> > matches[MAX]; // the 2 pairs (right, strength) of a given left
	vector<int> inverse[MAX]; // the left values with a right value of i
	vector<pair<int, pair<int, int> > > g[MAX]; // [dest, [w1, w2]]
	bool v[MAX];
 
	for (int i : students) {
		lefts.insert(l[i]);
		rights.insert(r[i]);
		matches[l[i]].push_back({r[i], s[i]});
		inverse[r[i]].push_back(l[i]);
	}
 
	for (int i : lefts) { 
		pair<int, int> e1 = matches[i][0];
		pair<int, int> e2 = matches[i][1];
		//cout << "left value: " << i << endl;
		//cout << "two rights: " << e1.first << " " << e2.first << endl;
		//cout << "strengths: " << e1.second << " " << e2.second << endl;
 
		g[e1.first].push_back({e2.first, {e1.second, e2.second}});
		g[e2.first].push_back({e1.first, {e2.second, e1.second}});
	}
 
	vector<int> choices;
	for (int i : rights) {
		if (v[i]) { continue; }
		// cout << "cycling from... " << i << endl;
		v[i] = true;
		int start = i;
		if (g[start][0].first == g[start][1].first && g[start][0].first == start) {
			choices.push_back(abs(g[start][0].second.first-g[start][0].second.second));
			// cout << "choices" << endl;
			// for (int i : choices) { cout << i << " "; } cout << endl;	
			continue;
		}
		else {
			// cout << "next level: " << i << endl;
			int sum1 = g[start][0].second.first;
			int sum2 = g[start][0].second.second;
			int last = start;
			int next = g[start][0].first;
			int its = 0;
			
			while (next != start) {
 
				v[next] = true;
				if (g[next][0].first != last) {
					sum1 += g[next][0].second.first;
					sum2 += g[next][0].second.second;
					last = next;
					next = g[next][0].first;
				}
				else if (g[next][1].first != last) {
					sum1 += g[next][1].second.first;
					sum2 += g[next][1].second.second;
					last = next;
					next = g[next][1].first;
				}
				else { 
					//cout << start << endl;
					//cout << g[start][0].second.first << " " << g[start][0].second.second << "." << endl;
					//cout << g[start][1].second.first << " " << g[start][1].second.second << "." << endl;
					sum1 = g[start][0].second.first + g[start][1].second.second;
					sum2 = g[start][1].second.first + g[start][0].second.second;
					//cout << sum1 << " " << sum2 << endl;
					break;
				}
			}
			choices.push_back(abs(sum1-sum2));
		}
	}
	int ct[600005];
	for (int i=0; i<600005; i++) { ct[i] = 0; }
 
	int t = 0;
	for (int i : choices) { ct[i]++; t += i; }
	for (int i=1; i<=600000; i++) {
		if (!ct[i]) { continue; }
		if (ct[i]%2) { ct[2*i] += ct[i]/2; ct[i] = 1; }
		else { ct[2*i] += ct[i]/2-1; ct[i] = 2; }
	}
	bitset<600005> dp;
	dp[0] = 1;
	for (int i=1; i<=600005; i++) {
		if (!ct[i]) { continue; }
		for (int j=0; j<ct[i]; j++) {
			dp |= (dp << i); 
		}
	}
	// cout << leftpts - rightpts << endl;
	for (int i=0; i<=600000; i++) {
		if (!dp[i]) { continue; }
		int score = (leftpts - rightpts) + i;
		int diff = abs(score - (t - i));
		// cout << i << " " << diff << endl;
		if (-k <= diff && diff <= k) {
			printf("YES\n"); return 0;
		}
	}
	printf("NO\n"); return 0;	
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:123:8: warning: unused variable 'its' [-Wunused-variable]
    int its = 0;
        ^
tug.cpp:21:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k; scanf("%d %d", &n, &k);
                                  ^
tug.cpp:24:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &l[i], &r[i], &s[i]);
                                         ^
tug.cpp:166:12: warning: iteration 600004u invokes undefined behavior [-Waggressive-loop-optimizations]
   if (!ct[i]) { continue; }
            ^
tug.cpp:165:17: note: containing loop
  for (int i=1; i<=600005; i++) {
                 ^

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