oj.uz

답안 #753307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753307 2023-06-05T03:28:37 Z boyliguanhan Tug of War (BOI15_tug) C++17
0 / 100
 26 ms 24164 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() {
    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({x,w});
        doi(i);
    }
    bt[sum+600000]=1;
    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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 20356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 20356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 26 ms 24164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 20356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -