Submission #1182234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182234		InvMOD	Tug of War (BOI15_tug)	C++17	100 / 100	501 ms	16584 KiB

tug

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;




void solve()
{
    int n,k; cin >> n >> k;

    vector<vector<int>> a(2 * n + 1, vector<int>(2,0)), deg(2 * n + 1, vector<int>(2, 0));

    vector<vector<vector<int>>> adj(2, vector<vector<int>>(2 * n + 1, vector<int>()));

    vector<int> w(2 * n + 1), item(1, 0);
    FOR(i, 1, 2 * n){
        FOR(j, 0, 1){
            cin >> a[i][j];
            deg[a[i][j]][j]++;
        }
        cin >> w[i];

        int l = a[i][0], r = a[i][1];
        adj[0][l].push_back(i);
        adj[1][r].push_back(i);
    }

    queue<pair<int,int>> q;
    FOR(i, 1, 2 * n){
        FOR(j, 0, 1){
            if(deg[i][j] == 1){
                q.emplace(j, i);
            }
        }
    }

    #define gw(x, t) (!t ? w[x] : -w[x])

    vector<bool> del(2 * n + 1, false); // remove all has (count(L,R)) as (1, 2), (1, 1), (2, 1)
    while(!q.empty()){
        pair<int,int> e = q.front(); q.pop();

        int t = e.fi, x = e.se;
        while(sz(adj[t][x])){
            int edge = adj[t][x].back(); adj[t][x].pop_back();

            if(del[edge]) continue;
            del[edge] = true;

            int t1 = t ^ 1, v = a[edge][t1];
            item.back() += gw(edge, t);
            --deg[x][t], --deg[v][t1];
            if(deg[v][t1] == 1) q.emplace(t1, v);
        }
    }
    if(!item.back()) item.pop_back();

    FOR(i, 1, 2 * n) FOR(j, 0, 1) if(deg[i][j] > 0 && deg[i][j] != 2){
        cout << "NO\n";
        return;
    }

    vector<vector<bool>> vis(2 * n + 1, vector<bool>(2, false));
    function<void(int,int,int)> get_item = [&](int x, int t, int cur_item) -> void{
        vis[x][t] = true;
        if(!deg[x][t]){
            while(sz(adj[t][x])) adj[t][x].pop_back();
            item.push_back(cur_item);
        }
        else{
            while(sz(adj[t][x])){
                int edge = adj[t][x].back(); adj[t][x].pop_back();

                if(del[edge]) continue;
                del[edge] = true;

                int t1 = t ^ 1, v = a[edge][t1];
                --deg[x][t], --deg[v][t1];

                if(deg[v][t1] <= 1) get_item(v, t1, cur_item + gw(edge, t));
            }
        }
    };

    FOR(i, 1, 2 * n) FOR(j, 0, 1) if(!vis[i][j]){
        if(deg[i][j] == 2){
            get_item(i, j, 0);
        }
    }

    #define gabs(x) (x < 0 ? -x : x)

    int sum = 0;
    for(int& x : item){
        x = gabs(x);
        sum += x;
    }

    const int MAX = 3e4 * 20 + 5;
    bitset<MAX> dp;

    dp[0] = 1;
    for(const int& x : item) dp |= (dp << x);

    for(int i = 0; i <= sum / 2; i++){
        if(dp[i]){
            if(sum - i * 2 <= k){
                cout << "YES\n";
                return;
            }
        }
    }
    cout << "NO\n";
    return;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

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

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