#include "bits/stdc++.h"
using namespace std;
bool del[2 * 30005];
int deg[2][30005];
vector <int> g[2][30005];
struct data
{
int l, r, s;
data () {}
data (int l, int r, int s) : l(l), r(r), s(s) {}
} a[2 * 30005];
struct node
{
int i, side;
node () {}
node (int i, int side) : i(i), side(side) {}
};
bool play[2 * 30010];
bool vis[2][30010];
int sum;
bool pl[2 * 30010];
bool vs[2][30010];
void cycle(node n) {
// cout << n.i << " " << n.side << endl;
if(n.side == -1) {
play[n.i] = true;
if(vis[0][a[n.i].l] == false) {
cycle(node(a[n.i].l, 0));
sum += a[n.i].s;
} else {
cycle(node(a[n.i].r, 1));
sum -= a[n.i].s;
}
} else {
vis[n.side][n.i] = true;
for(auto i : g[n.side][n.i]) {
if(del[i] == false && play[i] == false) {
cycle(node(i, -1));
break;
}
}
}
}
void loop(node n) {
if(n.side == -1) {
pl[n.i] = true;
if(vs[1][a[n.i].r] == false) {
loop(node(a[n.i].r, 1));
sum -= a[n.i].s;
} else {
loop(node(a[n.i].l, 0));
sum += a[n.i].s;
}
} else {
vs[n.side][n.i] = true;
for(auto i : g[n.side][n.i]) {
if(del[i] == false && pl[i] == false) {
loop(node(i, -1));
break;
}
}
}
}
int main(int argc, char const *argv[])
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 1; i <= n+n; i++) {
int l, r, s;
scanf("%d %d %d", &l, &r, &s);
a[i] = data(l, r, s);
g[0][l].push_back(i);
g[1][r].push_back(i);
++deg[0][l];
++deg[1][r];
}
queue <node> Q;
for(int i = 1; i <= n; i++) {
if(deg[0][i] == 1) Q.push(node(i, 0));
if(deg[1][i] == 1) Q.push(node(i, 1));
if(deg[0][i] == 0 || deg[1][i] == 0) {
printf("NO\n");
exit(0);
}
}
int add[2];
add[0] = add[1] = 0;
while(!Q.empty()) {
node p = Q.front();
Q.pop();
for(auto i : g[p.side][p.i]) {
if(del[i] == false) {
add[p.side] += a[i].s;
del[i] = true;
if(p.side == 0) {
--deg[1][a[i].r];
if(deg[1][a[i].r] == 1) {
Q.push(node(a[i].r, 1));
}
if(deg[1][a[i].r] == 0) {
printf("NO\n");
exit(0);
}
} else {
--deg[0][a[i].l];
if(deg[0][a[i].l] == 1) {
Q.push(node(a[i].l, 0));
}
if(deg[0][a[i].l] == 0) {
printf("NO\n");
exit(0);
}
}
}
}
}
for(int i = 1; i <= n+n; i++) {
if(play[i] == false) {
int k1, k2;
sum = 0;
cycle(node(i, -1));
k1 = sum;
sum = 0;
loop(node(i, -1));
k2 = sum;
assert(k1 == -k2);
}
}
return 0;
}
Compilation message
tug.cpp: In function 'int main(int, const char**)':
tug.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
^
tug.cpp:76:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &l, &r, &s);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
5320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
