Submission #1270675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270675		BuiDucManh123	Tug of War (BOI15_tug)	C++20	0 / 100	64 ms	2120 KiB

tug

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define ld long double
const int mod = 1e9+7;
using namespace std;
int vis[60009], sum, a[60009], b[60009], check[60009];
vector<pii> g[60009];
pii dfs(int u){
    int x = 0, y = 0;
    check[u] = 1;
    for(pii v : g[u]){
        if(vis[v.se]) continue;
        vis[v.se] = 1;
        pii res = dfs(v.fi);
        y += res.fi;
        x += res.se;
        x += b[v.se];
    }
    return {x, y};
}
signed main() {
    if (fopen(taskname".inp","r")) {
        freopen(taskname".inp","r",stdin);
        freopen(taskname".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    int total = 0;
    for(int i = 1; i <= 2 * n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        v += n;
        g[u].pb({v, i});
        g[v].pb({u, i});
        b[i] = w;
        total += w;
    }
    int m = 0;
    for(int i = 1; i <= 2 * n; i++){
        if(!check[i]){
            pii res = dfs(i);
            sum += res.fi;
            a[++m] = res.se - res.fi;
            //cout << res.fi << " " << res.se << "\n";
        }
    }
    //for(int i = 1; i <= m; i++)
    bitset<600009> dp;
    dp[0] = 1;
    sort(a + 1, a + m + 1, greater<>());
    for(int i = 1; i <= m; i++){
        dp |= (dp << a[i]);
    }
    for(int i = (total - k + 1) / 2; i <= (total + k + 1) / 2; i++){
        if(i >= sum && dp[i - sum] == 1){
            //cout << sum << "\n";
            //if(i - sum == 6) cout << "hehe";
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(taskname".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tug.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(taskname".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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