# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198445 | dndhk | Tug of War (BOI15_tug) | C++14 | 265 ms | 3192 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 pb push_back
using namespace std;
const int MAX_N = 60000;
typedef pair<int, int> pii;
int N, K;
int c[MAX_N+1];
vector<pii> gp[MAX_N+1];
bool chk[MAX_N+1];
bool vst[MAX_N+1];
int S;
vector<int> vt;
vector<pii> v;
bitset<MAX_N*10+1> bt;
bool dfs(int x){
vst[x] = true;
for(pii i : gp[x]){
if(chk[i.second]) continue;
chk[i.second] = true;
if(vst[i.first]){
int sum = 0;
if(x>N) sum+=c[i.second];
else sum-=c[i.second];
while(!v.empty()){
if(v.back().first>N){
sum+=v.back().second;
}else{
sum-=v.back().second;
}
if(v.back().first==i.first){
vt.pb((sum>0?sum:-sum));
sum = 0;
}
v.pop_back();
}
S+=sum;
}else{
v.pb({x, c[i.second]});
dfs(i.first);
}
return true;
}
return false;
}
int main(){
scanf("%d%d", &N, &K);
for(int i=1; i<=N*2; i++){
int l, r;
scanf("%d%d%d", &l, &r, &c[i]);
r+=N;
gp[l].pb({r, i});
gp[r].pb({l, i});
}
for(int i=1; i<=N*2; i++){
if(!vst[i]){
if(!dfs(i)){
printf("NO");
return 0;
}
}
}
int S2 = 0;
for(int i : vt) S2 += i;
bt[0] = true;
int s = max(0, (S2-K-S+1)/2), e = (S2-S+K)/2;
for(int i : vt){
bt = (bt | (bt<<i));
}
for(int j=s; j<=e; j++){
if(bt[j]){
printf("YES");
return 0;
}
}
printf("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... |