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>
using namespace std;
#define fr first
#define sc second
const int mxn=3e4+5;
int n,k,f[mxn*2][2],ans=0,st[mxn*2],res=0;
set<int>s[mxn*2];
set<pair<int,int> >g;
bool mark[mxn*2];
vector<int>nk;
void dfs(int z,int dis){
mark[z]=1;
int x=*s[z].begin();
res+=(dis&1)?-st[x]:st[x];
s[z].erase(x);
int y=(z>mxn)?f[x][0]:f[x][1]+mxn;
s[y].erase(x);
if(!mark[y])
dfs(y,dis+1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n*2;i++){
int x,y;
cin>>x>>y>>st[i];
s[x].insert(i);
s[y+mxn].insert(i);
f[i][0]=x;
f[i][1]=y;
}
for(int i=1;i<=n;i++){
g.insert({s[i].size(),i});
g.insert({s[i+mxn].size(),i+mxn});
}
while(g.size() && g.begin()->fr!=2){
if(g.begin()->fr==0){
cout<<"NO";
return 0;
}
int x=g.begin()->sc;
int y=*s[x].begin();
s[x].erase(y);
int z=(x>mxn)?f[y][0]:f[y][1]+mxn;
s[z].erase(y);
g.erase({1,x});
g.erase({s[z].size()+1,z});
g.insert({s[z].size(),z});
if(x>mxn)ans+=st[y];
else ans-=st[y];
}
for(int i=1;i<=n;i++){
if(!s[i].size() || mark[i])continue;
res=0;
dfs(i,0);
nk.push_back(res);
}
for(int i=1+mxn;i<=n+mxn;i++){
if(!s[i].size() || mark[i])continue;
res=0;
dfs(i,0);
nk.push_back(res);
}
const int gg=20*3000+5,ggg=gg*2;
bitset<ggg>b[2];
b[0][ans+gg]=1;
for(int i=1;i<=nk.size();i++){
int j=i&1,x=nk[i-1];
b[j]=((b[j^1]<<x)|(b[j^1]>>x));
}
for(int i=gg-k;i<=gg+k;i++){
if(b[nk.size()&1][i]){
cout<<"YES";
return 0;
}
}
cout<<"NO";
return 0;
}
Compilation message (stderr)
tug.cpp: In function 'int main()':
tug.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i=1;i<=nk.size();i++){
| ~^~~~~~~~~~~
# | 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... |