Submission #136993

#	Time	Username	Problem	Language	Result	Execution time	Memory
136993		Gustav	Tug of War (BOI15_tug)	C++14	71 / 100	3037 ms	20940 KiB

tug

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod1 = 1000000007;
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())

int n, k;
vector<vpi> adj;
vi visited;
vi starts;
int constup = 0, constdown = 0;

bool findcycle(int node, int parent, bool found){
    if(visited[node]){
        if(!found) starts.push_back(node);
        return true;
    }
    visited[node] = 1;
    for(auto x : adj[node]){
        if(x.first != parent)
            found |= findcycle(x.first, node, found);
    }
    return found;
}

pair<bool, pi> dfs(int node, int parent){
    visited[node] = 1;
    int sumup = 0;
    int sumdown = 0;
    bool toparent = false;
    bool cycle = false;
    for(auto x : adj[node]){
        if(visited[x.first]){
            if(parent == -1){
                if(node >= n) sumup += x.second;
                else sumdown += x.second;
            }
            if(parent != x.first) cycle = true;
            else if(toparent) cycle = true;
            else toparent = true;
            continue;
        }
        pair<bool, pi> r = dfs(x.first, node);
        if(!r.first){
            if(node < n) constup += x.second;
            else constdown += x.second;
            continue;
        }
        cycle = true;
        sumup += r.second.first;
        sumdown += r.second.second;
        if(node < n) sumup += x.second;
        else sumdown += x.second;
    }
    return {cycle, {sumup, sumdown}};
}

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

    cin >> n >> k;
    adj = vector<vpi>(2*n);
    int strengthsum = 0;
    for(int i = 0; i < 2*n; i++){
        int l, r, s;
        cin >> l >> r >> s;
        l--,r--;
        r+=n;
        adj[l].emplace_back(r, s);
        adj[r].emplace_back(l, s);
        strengthsum += s;
    }
    visited = vi(2*n);
    for(int i = 0; i < 2*n; i++){
        if(!visited[i] && !findcycle(i, -1, false)){
            cout << "NO\n";
            return 0;
        }
    }
    visited = vi(2*n);
    int diff = 0;
    vi alts(3000000);
    for(int x : starts){
        pair<bool, pi> r = dfs(x, -1);
        alts[2*(r.second.second - r.second.first)+1500000]++;
        diff += r.second.first - r.second.second;
    }
    diff += constup-constdown;
    int from = -k-diff;
    int to = k-diff;
    gp_hash_table<int, int> p;
    p[0] = 1;
    for(int i = 0; i < 3000000; i++){
        if(alts[i] == 0) continue;
        vi a;
        for(auto x : p){
            a.push_back(x.first);
        }
        for(int x : a){
            for(int j = 1; j <= alts[i]; j++){
                p[x+(i-1500000)*j] = 1;
            }
        }
    }
    bool ans = false;
    for(auto x : p){
        if(x.first >= from && x.first <= to) ans = true;
    }
    if(ans) cout << "YES\n";
    else cout << "NO\n";
}

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