Submission #403194

#	Time	Username	Problem	Language	Result	Execution time	Memory
403194		gevacrt	Tug of War (BOI15_tug)	C++17	100 / 100	1659 ms	29756 KiB

tug

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int N, K;
vector<unordered_set<int>> adj; vi S;

int TOT = 0, CNT = 0;
void remove_singular(int x){
    auto u = *adj[x].begin(); adj[x].clear();
    adj[u].erase(x);

    if(x < 3*N) TOT += S[u], CNT++;
    else CNT--;

    auto v = *adj[u].begin(); adj[u].clear();
    adj[v].erase(u);

    if(adj[v].size() == 1) remove_singular(v);    
}

vi vis;
void dfs(int u, int c, int h[]){
    h[c] += S[u]; vis[u] = 1;

    for(auto v : adj[u]){
        if(vis[v]) continue;
        dfs(v, (c+1)%4, h);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;

    adj.resize(4*N); S.resize(4*N);
    for(int x = 0; x < 2*N; x++){
        int l, r; cin >> l >> r >> S[x];
        l--, r--; r += N;

        adj[x].insert(2*N+l);
        adj[2*N+l].insert(x);
    
        adj[x].insert(2*N+r);
        adj[2*N+r].insert(x);
    }

    // find single nodes
    for(int x = 2*N; x < 4*N; x++){
        if(adj[x].size() == 1)
            remove_singular(x);
    }

    for(int x = 2*N; x < 4*N; x++){
        if(adj[x].size() != 2 and adj[x].size() != 0){
            cout << "NO" << endl; return 0;
        }
    }
    assert(CNT == 0);

    bitset<600010> KP;
    KP[TOT] = 1;

    vis.resize(4*N);
    for(int x = 0; x < 2*N; x++){
        if(adj[x].empty() or vis[x]) continue;
        int h[4] = {}; dfs(x, 0, h);

        KP = (KP<<h[0]) | (KP<<h[2]);
    }
    
    int SUN = accumulate(all(S), 0);
    for(int i = 0; i < 600010; i++){
        if(KP[i]&1 and abs(SUN-2*i) <= K){
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";

    return 0;
}

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