Submission #1270684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270684		BuiDucManh123	Tug of War (BOI15_tug)	C++20	100 / 100	410 ms	7652 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;
#define int ll
int type[600009], vis[600009], par[600009], a[600009], m, sum, total, c[600009], n, k;
pii b[600009];
vector<int> path, record;
vector<pii> g[600009];
bool dfs(int u, int p, int pre){
    record.pb(u);
    vis[u] = 1;
    for(pii v : g[u]){
        if(v.fi == p && v.se == pre) continue;
        if(vis[v.fi]){
            path.pb(u);
            while(u != v.fi){
                u = par[u];
                path.pb(u);
            }
            type[v.fi] = v.se;
            return true;
        }
        type[v.fi] = v.se;
        par[v.fi] = u;
        if(dfs(v.fi, u, v.se)) return true;
    }
    return false;
}
void cal(int u){
    vis[u] = 1;
    for(pii v : g[u]){
        if(vis[v.fi]) continue;
        if(v.fi > n){
            sum += a[v.se];
        }
        cal(v.fi);
    }
}
void solve(int u){
    path.clear();
    record.clear();
    dfs(u, 0, -1);
    int x = 0, y = 0;
    for(int i = 0; i < path.size(); i++){
        if(i & 1){
            x += a[type[path[i]]];
        }else{
            y += a[type[path[i]]];
        }
    }
    if(x > y) swap(x, y);
    sum += x;
    c[++m] = y - x;
    for(int x : record) vis[x] = 0;
    if(path.size() == 0) path.pb(u);
    for(int x : path) vis[x] = 1;
    for(int v : path){
        cal(v);
    }

}
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);
    cin >> n >> k;
    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});
        a[i] = w;
        total += w;
    }
    for(int i = 1; i <= 2 * n; i++){
        if(!vis[i]){
            solve(i);
        }
    }
    ///*
    bitset<600009> dp;
    dp[0] = 1;
    for(int i = 1; i <= m; i++){
        dp |= (dp << c[i]);
    }
    for(int i = 0; i <= total; i++){
        if(i >= sum && dp[i - sum] && abs((total - i) - i) <= k){
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    //*/
    return 0;
}

Compilation message (stderr)

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

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