oj.uz

Submission #952555

# Submission time Handle Problem Language Result Execution time Memory
952555 2024-03-24T08:45:21 Z PM1 Tug of War (BOI15_tug) C++17
23 / 100
 297 ms 7260 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[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

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++){
      |              ~^~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Incorrect 2 ms 4184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Incorrect 2 ms 4184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 7196 KB Output is correct
2 Correct 12 ms 7004 KB Output is correct
3 Correct 289 ms 7180 KB Output is correct
4 Correct 10 ms 7000 KB Output is correct
5 Correct 291 ms 7180 KB Output is correct
6 Correct 9 ms 7004 KB Output is correct
7 Correct 287 ms 7176 KB Output is correct
8 Correct 10 ms 7004 KB Output is correct
9 Correct 285 ms 7152 KB Output is correct
10 Correct 9 ms 7200 KB Output is correct
11 Correct 281 ms 7252 KB Output is correct
12 Correct 9 ms 7004 KB Output is correct
13 Correct 290 ms 7152 KB Output is correct
14 Correct 291 ms 7172 KB Output is correct
15 Correct 9 ms 7004 KB Output is correct
16 Correct 286 ms 7172 KB Output is correct
17 Correct 9 ms 7256 KB Output is correct
18 Correct 297 ms 7168 KB Output is correct
19 Correct 10 ms 6960 KB Output is correct
20 Correct 285 ms 7000 KB Output is correct
21 Correct 13 ms 7000 KB Output is correct
22 Correct 156 ms 7260 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Incorrect 2 ms 4184 KB Output isn't correct
3 Halted 0 ms 0 KB -