oj.uz

Submission #406319

# Submission time Handle Problem Language Result Execution time Memory
406319 2021-05-17T11:21:13 Z codebuster_10 Tug of War (BOI15_tug) C++17
0 / 100
 21 ms 5956 KB 
#include <bits/stdc++.h>

using namespace std ;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  #ifdef ONLINE_JUDGE
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
  #define __f(...) 0
  #endif
}

void err(bool flag){cout << (flag?"YES":"NO"); exit(0);}

const int MAX_N = 2 * 30000 + 1;
multiset<pr<int,int>> g[MAX_N];
vt<bool> vis(MAX_N,false);
bitset<MAX_N> is;
int tot = 0;

void dfs(int i) {
	vis[i] = true;
	if (!sz(g[i])) return;
	auto [nxt,cost] = *g[i].begin();
	tot += cost;
	if (!vis[nxt]) {
		g[nxt].erase(g[nxt].find({i, -cost}));
		g[i].clear();
		dfs(nxt);
	}
}


signed main(){
  setIO() ;
	int n,k; rd(n,k);
	f(id,0,2*n){
		int l,r,s; rd(l,r,s);
		--l,--r;
		g[l].insert({r+n,s});
		g[r+n].insert({l,-s});
	}
	// keep removing those with degree one.
	queue<int> q;
	f(i,0,n){
		if(sz(g[i]) == 1) q.push(i);
		else if(sz(g[i]) == 0) err(0);
	}
	
	while(sz(q)){
		int now = q.front(); q.pop();
		if(!sz(g[now])) err(0);
		auto [nxt,cost] = *g[now].begin();
		tot += cost;
		g[now].clear();
		g[nxt].erase(g[nxt].find({now,-cost}));
	}
	
	vt<int> W;
	if(tot) W.pb(abs(tot));
	
	
	f(i,0,n) if(!vis[i] && sz(g[i])){
		tot = 0;
		g[i].erase(g[i].begin());
		dfs(i);
		if(tot) W.pb(abs(tot));
	}
	
	int sum = accumulate(all(W),0);
	is[0] = true;
	for(auto i : W) is |= (is << i);
	f(i,0,MAX_N){
		if(abs(sum - 2*i) <= k && is[i]) err(1);
	}
	err(0);
	
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3152 KB Output is correct
2 Correct 3 ms 3148 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 3 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 2 ms 3148 KB Output is correct
11 Correct 2 ms 3148 KB Output is correct
12 Correct 2 ms 3148 KB Output is correct
13 Correct 3 ms 3276 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 3 ms 3148 KB Output is correct
16 Correct 3 ms 3156 KB Output is correct
17 Correct 3 ms 3148 KB Output is correct
18 Correct 3 ms 3148 KB Output is correct
19 Correct 3 ms 3148 KB Output is correct
20 Correct 2 ms 3152 KB Output is correct
21 Correct 3 ms 3148 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Incorrect 3 ms 3152 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3152 KB Output is correct
2 Correct 3 ms 3148 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 3 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 2 ms 3148 KB Output is correct
11 Correct 2 ms 3148 KB Output is correct
12 Correct 2 ms 3148 KB Output is correct
13 Correct 3 ms 3276 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 3 ms 3148 KB Output is correct
16 Correct 3 ms 3156 KB Output is correct
17 Correct 3 ms 3148 KB Output is correct
18 Correct 3 ms 3148 KB Output is correct
19 Correct 3 ms 3148 KB Output is correct
20 Correct 2 ms 3152 KB Output is correct
21 Correct 3 ms 3148 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Incorrect 3 ms 3152 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5896 KB Output is correct
2 Correct 15 ms 5852 KB Output is correct
3 Correct 14 ms 5836 KB Output is correct
4 Correct 14 ms 5836 KB Output is correct
5 Correct 15 ms 5836 KB Output is correct
6 Correct 14 ms 5888 KB Output is correct
7 Correct 14 ms 5836 KB Output is correct
8 Correct 17 ms 5956 KB Output is correct
9 Correct 15 ms 5836 KB Output is correct
10 Correct 18 ms 5784 KB Output is correct
11 Correct 14 ms 5844 KB Output is correct
12 Correct 14 ms 5836 KB Output is correct
13 Correct 13 ms 5844 KB Output is correct
14 Correct 13 ms 5836 KB Output is correct
15 Correct 13 ms 5856 KB Output is correct
16 Correct 13 ms 5892 KB Output is correct
17 Correct 14 ms 5836 KB Output is correct
18 Correct 13 ms 5852 KB Output is correct
19 Correct 13 ms 5864 KB Output is correct
20 Correct 17 ms 5836 KB Output is correct
21 Correct 20 ms 5868 KB Output is correct
22 Incorrect 21 ms 5936 KB Output isn't correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3152 KB Output is correct
2 Correct 3 ms 3148 KB Output is correct
3 Correct 2 ms 3148 KB Output is correct
4 Correct 3 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 2 ms 3148 KB Output is correct
11 Correct 2 ms 3148 KB Output is correct
12 Correct 2 ms 3148 KB Output is correct
13 Correct 3 ms 3276 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 3 ms 3148 KB Output is correct
16 Correct 3 ms 3156 KB Output is correct
17 Correct 3 ms 3148 KB Output is correct
18 Correct 3 ms 3148 KB Output is correct
19 Correct 3 ms 3148 KB Output is correct
20 Correct 2 ms 3152 KB Output is correct
21 Correct 3 ms 3148 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Incorrect 3 ms 3152 KB Output isn't correct
24 Halted 0 ms 0 KB -