Submission #753844

#	Time	Username	Problem	Language	Result	Execution time	Memory
753844		vjudge1	Tug of War (BOI15_tug)	C++17	100 / 100	2116 ms	16484 KiB

tug

#include<bits/stdc++.h>
#pragma GCC optimzize(2)
#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(adj[nxt].find({n, cost}));
		adj[n].clear();
		dfs(nxt, N);
	}
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    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(adj[i].find({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 (stderr)

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

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29