Submission #753849

#	Time	Username	Problem	Language	Result	Execution time	Memory
753849		boyliguanhan	Tug of War (BOI15_tug)	C++17	100 / 100	1873 ms	16584 KiB

tug

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("Ofast,inline")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("movbe")
#pragma GCC target("aes,pclmul,rdrnd")
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
#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;
inline int read() { 
    int v = 0;
    int sign = 1;
    char c = getchar();
    if (c == '-') { 
        sign = -1;
    } else {
        v += c - '0';
    }
    while ((c = getchar()) != EOF && c != ' ' && c != '\n') {
        v *= 10; v += c - '0'; 
    }
    return v * sign;
}
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() {
    int n(read()), k(read()), sum = 0;
    n*=2;
    for(int i = 1; i <= n; i++) {
        int x(read()), y(read()), w(read());
        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: In function 'void dfs(int, int)':
tug.cpp:38:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   38 |     else
      |     ^~~~
tug.cpp:40:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   40 |  if (!del[nxt]) {
      |  ^~

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