제출 #25190

#제출 시각아이디문제언어결과실행 시간메모리
25190minimarioTug of War (BOI15_tug)C++14
41 / 100
56 ms15836 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 30005; set<int> left1[MAX]; set<int> right1[MAX]; int l[MAX], r[MAX], s[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<600050> dp; dp[0] = 1; for (int i=1; i<=40; 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; }

컴파일 시 표준 에러 (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]);
                                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...