#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;
}
}
printf("YES\n"); return 0;
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));
}
}
/*
cout << choices.size() << endl;
for (int i : choices) {
cout << i << endl;
}
*/
}
Compilation message
tug.cpp: In function 'int main()':
tug.cpp:124: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 time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 2 |
Correct |
23 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 4 |
Correct |
33 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 6 |
Correct |
26 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 8 |
Correct |
26 ms |
8192 KB |
Output is correct |
| 9 |
Correct |
26 ms |
9248 KB |
Output is correct |
| 10 |
Correct |
23 ms |
8192 KB |
Output is correct |
| 11 |
Correct |
26 ms |
9248 KB |
Output is correct |
| 12 |
Correct |
23 ms |
8192 KB |
Output is correct |
| 13 |
Correct |
19 ms |
9248 KB |
Output is correct |
| 14 |
Correct |
29 ms |
9248 KB |
Output is correct |
| 15 |
Correct |
23 ms |
8192 KB |
Output is correct |
| 16 |
Correct |
33 ms |
9248 KB |
Output is correct |
| 17 |
Correct |
23 ms |
8192 KB |
Output is correct |
| 18 |
Correct |
23 ms |
9248 KB |
Output is correct |
| 19 |
Correct |
33 ms |
8192 KB |
Output is correct |
| 20 |
Correct |
33 ms |
9248 KB |
Output is correct |
| 21 |
Correct |
23 ms |
8192 KB |
Output is correct |
| 22 |
Correct |
39 ms |
9248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
5420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
