oj.uz

Submission #753305

# Submission time Handle Problem Language Result Execution time Memory
753305 2023-06-05T03:25:43 Z boyliguanhan Tug of War (BOI15_tug) C++17
23 / 100
 783 ms 12664 KB 
#include<bits/stdc++.h>
#define doi(i) if(!adj[i].size()) {cout << "NO\n";return 0;}if(adj[i].size()<2) {q.push(i);sum+=(i>n/2?1:-1)*((*begin(adj[i])).second);}
#define shift(x) ((x)>0?bt<<(x):bt>>(-x))
using namespace std;
multiset<pair<int, int>> adj[200100];
queue<int> q;
bool del[200100];
bitset<1200000> bt;
int tot;
void dfs(int n, int N) {
	if (del[n]) return;
	del[n] = true;
	int nxt, cost;
	tie(nxt, cost) = *adj[n].begin();
    if(nxt>N)
	    tot += cost;
    else
        tot-=cost;
	if (!del[nxt]) {
		adj[nxt].erase({n, cost});
		adj[n].clear();
		dfs(nxt, N);
	}
}
int main() {
    int n, k, sum = 0;
    cin >> n >> k;
    n*=2;
    for(int i = 1; i <= n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        y+=n/2;
        adj[x].insert({y,w});
        adj[y].insert({x,w});
    }
    for(int i = 1; i <= n; i++) {
        doi(i);
    }
    while(q.size()) {
        int x = q.front(), i = (*adj[x].begin()).first, w= (*adj[x].begin()).second;
        del[x] = 1;
        q.pop();
        adj[i].erase({x,w});
        doi(i);
    }
    bt[sum+600000]=1;
    for(int i = 1; i <= n; i++) {
        if(!del[i]) {
            tot = 0;
            adj[i].erase(adj[i].begin());
            dfs(i, n/2);
            bt = shift(tot)|shift(-tot);
        }
    }
    for(int i = -k; i <= k; i++) {
        if(bt[600000+i]) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
}

Compilation message

tug.cpp: In function 'void dfs(int, int)':
tug.cpp:17:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   17 |     else
      |     ^~~~
tug.cpp:19:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   19 |  if (!del[nxt]) {
      |  ^~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10324 KB Output is correct
2 Correct 7 ms 10444 KB Output is correct
3 Correct 6 ms 10324 KB Output is correct
4 Correct 6 ms 10396 KB Output is correct
5 Correct 6 ms 10324 KB Output is correct
6 Incorrect 6 ms 10400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10324 KB Output is correct
2 Correct 7 ms 10444 KB Output is correct
3 Correct 6 ms 10324 KB Output is correct
4 Correct 6 ms 10396 KB Output is correct
5 Correct 6 ms 10324 KB Output is correct
6 Incorrect 6 ms 10400 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 12544 KB Output is correct
2 Correct 27 ms 12216 KB Output is correct
3 Correct 721 ms 12664 KB Output is correct
4 Correct 23 ms 12236 KB Output is correct
5 Correct 674 ms 12548 KB Output is correct
6 Correct 22 ms 12244 KB Output is correct
7 Correct 706 ms 12544 KB Output is correct
8 Correct 22 ms 12244 KB Output is correct
9 Correct 705 ms 12536 KB Output is correct
10 Correct 23 ms 12204 KB Output is correct
11 Correct 700 ms 12560 KB Output is correct
12 Correct 23 ms 12108 KB Output is correct
13 Correct 783 ms 12568 KB Output is correct
14 Correct 734 ms 12544 KB Output is correct
15 Correct 23 ms 12244 KB Output is correct
16 Correct 703 ms 12540 KB Output is correct
17 Correct 26 ms 12124 KB Output is correct
18 Correct 699 ms 12544 KB Output is correct
19 Correct 30 ms 12144 KB Output is correct
20 Correct 681 ms 12540 KB Output is correct
21 Correct 24 ms 12148 KB Output is correct
22 Correct 348 ms 12644 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10324 KB Output is correct
2 Correct 7 ms 10444 KB Output is correct
3 Correct 6 ms 10324 KB Output is correct
4 Correct 6 ms 10396 KB Output is correct
5 Correct 6 ms 10324 KB Output is correct
6 Incorrect 6 ms 10400 KB Output isn't correct
7 Halted 0 ms 0 KB -