oj.uz

답안 #753847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753847 2023-06-06T07:51:07 Z boyliguanhan Tug of War (BOI15_tug) C++17
0 / 100
 15 ms 11976 KB 
#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

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]) {
      |  ^~
tug.cpp: In function 'int main()':
tug.cpp:50:15: warning: unnecessary parentheses in declaration of 'read' [-Wparentheses]
   50 |         int x,(read()), y(read()), w(read());
      |               ^
tug.cpp:50:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |         int x,(read()), y(read()), w(read());
      |             ^

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Incorrect 6 ms 10068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Incorrect 6 ms 10068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 11976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Incorrect 6 ms 10068 KB Output isn't correct
3 Halted 0 ms 0 KB -