# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
310598 | Ruxandra985 | Tug of War (BOI15_tug) | C++14 | 1085 ms | 9752 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DIMN 30010
using namespace std;
int n;
int f[4 * DIMN] , gr[4 * DIMN];
vector <pair <int , int> > v[4 * DIMN];
deque <int> dq;
bitset <20 * DIMN> rcs;
void dfs (int nod , int &val){
int i , vecin , cst;
f[nod] = 1;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
cst = v[nod][i].second;
if (f[vecin])
continue;
if (vecin > 2 * n && vecin <= 3 * n){ /// il bagi in a
val += cst;
}
else if (vecin > 3 * n) { /// il bagi in b
val -= cst;
}
dfs (vecin , val);
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int k , i , x , y , z , a = 0 , b = 0 , nod , vecin , cst , val , sum = 0;
fscanf (fin,"%d%d",&n,&k);
for (i = 1 ; i <= 2 * n ; i++){
fscanf (fin,"%d%d%d",&x,&y,&z);
v[i].push_back(make_pair(2 * n + x , z));
v[2 * n + x].push_back(make_pair(i , z));
v[i].push_back(make_pair(3 * n + y , z));
v[3 * n + y].push_back(make_pair(i , z));
gr[2 * n + x]++;
gr[3 * n + y]++;
}
for (i = 2 * n + 1 ; i <= 4 * n ; i++){
if (gr[i] == 1){
dq.push_back(i);
}
}
while (!dq.empty()){
nod = dq.front();
dq.pop_front();
f[nod] = 1; /// pozitia asta a fost luata
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
cst = v[nod][i].second;
if (!f[vecin]){
f[vecin] = 1;
if (nod <= 3 * n)
a += cst;
else b += cst;
nod = vecin;
break;
}
}
/// nod = omul
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
gr[vecin]--;
if (gr[vecin] == 1){
dq.push_back(vecin);
}
}
}
/// faci ce este obligatoriu
rcs[0] = 1;
for (i = 1 ; i <= 2 * n ; i++){
if (!f[i]){
val = 0;
dfs (i , val);
/// val = o valoare a unui cuplaj din punctul asta
val = max(val , -val);
sum += val;
rcs = (rcs | (rcs << val));
///rcs e un rucsac. rcs[i] = 1 inseamna ca exista o suma de idk cate
///cuplaje care da i (in modul toate)
}
}
for (i = 1 ; i <= 4 * n ; i++){
if (!f[i]){
fprintf (fout,"NO");
return 0;
}
}
/// aleg un numar de cuplaje din astea si le iau valorile negative in loc
/// de cele pozitive
for (i = 0 ; i <= 20 * n ; i++){
if (rcs[i] && max( (a - b + sum - 2 * i) , -(a - b + sum - 2 * i) ) <= k){
fprintf (fout,"YES");
return 0;
}
}
fprintf (fout,"NO");
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |