oj.uz

Submission #406320

# Submission time Handle Problem Language Result Execution time Memory
406320 2021-05-17T11:25:10 Z codebuster_10 Tug of War (BOI15_tug) C++17
0 / 100
 21 ms 5752 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}));
		if(sz(g[nxt]) == 1) q.push(nxt);
	}
	
	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 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 2 ms 3148 KB Output is correct
6 Correct 2 ms 3048 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 2 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 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 2 ms 3148 KB Output is correct
14 Correct 2 ms 3148 KB Output is correct
15 Correct 3 ms 3148 KB Output is correct
16 Correct 2 ms 3148 KB Output is correct
17 Correct 3 ms 3100 KB Output is correct
18 Correct 2 ms 3148 KB Output is correct
19 Correct 2 ms 3148 KB Output is correct
20 Correct 2 ms 3148 KB Output is correct
21 Correct 2 ms 3148 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Incorrect 2 ms 3148 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 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 2 ms 3148 KB Output is correct
6 Correct 2 ms 3048 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 2 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 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 2 ms 3148 KB Output is correct
14 Correct 2 ms 3148 KB Output is correct
15 Correct 3 ms 3148 KB Output is correct
16 Correct 2 ms 3148 KB Output is correct
17 Correct 3 ms 3100 KB Output is correct
18 Correct 2 ms 3148 KB Output is correct
19 Correct 2 ms 3148 KB Output is correct
20 Correct 2 ms 3148 KB Output is correct
21 Correct 2 ms 3148 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Incorrect 2 ms 3148 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5540 KB Output is correct
2 Correct 14 ms 5592 KB Output is correct
3 Correct 13 ms 5580 KB Output is correct
4 Correct 14 ms 5580 KB Output is correct
5 Correct 17 ms 5580 KB Output is correct
6 Correct 16 ms 5632 KB Output is correct
7 Correct 16 ms 5596 KB Output is correct
8 Correct 15 ms 5580 KB Output is correct
9 Correct 15 ms 5668 KB Output is correct
10 Correct 13 ms 5660 KB Output is correct
11 Correct 13 ms 5580 KB Output is correct
12 Correct 13 ms 5580 KB Output is correct
13 Correct 13 ms 5580 KB Output is correct
14 Correct 16 ms 5660 KB Output is correct
15 Correct 16 ms 5596 KB Output is correct
16 Correct 13 ms 5564 KB Output is correct
17 Correct 14 ms 5604 KB Output is correct
18 Correct 15 ms 5580 KB Output is correct
19 Correct 14 ms 5752 KB Output is correct
20 Correct 14 ms 5556 KB Output is correct
21 Correct 13 ms 5580 KB Output is correct
22 Incorrect 21 ms 5600 KB Output isn't correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 2 ms 3148 KB Output is correct
6 Correct 2 ms 3048 KB Output is correct
7 Correct 2 ms 3148 KB Output is correct
8 Correct 2 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 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 2 ms 3148 KB Output is correct
14 Correct 2 ms 3148 KB Output is correct
15 Correct 3 ms 3148 KB Output is correct
16 Correct 2 ms 3148 KB Output is correct
17 Correct 3 ms 3100 KB Output is correct
18 Correct 2 ms 3148 KB Output is correct
19 Correct 2 ms 3148 KB Output is correct
20 Correct 2 ms 3148 KB Output is correct
21 Correct 2 ms 3148 KB Output is correct
22 Correct 2 ms 3148 KB Output is correct
23 Incorrect 2 ms 3148 KB Output isn't correct
24 Halted 0 ms 0 KB -