| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 952566 |
2024-03-24T09:06:08 Z |
PM1 |
Tug of War (BOI15_tug) |
C++17 |
|
296 ms |
13908 KB |
#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);
if(res<0)res*=-1;
nk.push_back(res);
}
const int gg=20*30000+5,ggg=gg*2;
bitset<ggg>b;
b[gg]=1;
for(int i=1;i<=nk.size();i++){
int x=nk[i-1];
b=((b<<x)|(b>>x));
}
for(int i=gg-k+ans;i<=gg+k+ans;i++){
if(b[i]){
assert(0);
cout<<"YES";
return 0;
}
}
cout<<"NO";
return 0;
}
Compilation message
tug.cpp: In function 'int main()':
tug.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int i=1;i<=nk.size();i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
13908 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
