Submission #729884

#	Time	Username	Problem	Language	Result	Execution time	Memory
729884		_martynas	Tug of War (BOI15_tug)	C++14	100 / 100	935 ms	7448 KiB

tug

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 30005;

int n, k;
int L[2*MXN], R[2*MXN], S[2*MXN];
bool visited[2*MXN];
vi at_l[MXN], at_r[MXN];
int deg_l[MXN], deg_r[MXN];
int diff0 = 0;

void impossible(string id = "") {
    //cout << "NO" << id << "\n";
    cout << "NO\n";
    exit(0);
}

int main() {
    FASTIO();
    cin >> n >> k;
    for(int i = 0; i < 2*n; i++) {
        cin >> L[i] >> R[i] >> S[i]; L[i]--, R[i]--;
        at_l[L[i]].PB(i);
        at_r[R[i]].PB(i);
        deg_l[L[i]]++, deg_r[R[i]]++;
    }
    queue<pii> Q;
    for(int i = 0; i < n; i++) {
        if(at_l[i].size() == 1) {
            int j = at_l[i].back();
            if(visited[j]) impossible("g");
            Q.push({j, 0});
            visited[j] = true;
            deg_l[i]--;
            diff0 += S[j];
        }
        if(at_r[i].size() == 1) {
            int j = at_r[i].back();
            if(visited[j]) impossible("h");
            Q.push({j, 1});
            visited[j] = true;
            deg_r[i]--;
            diff0 -= S[j];
        }
    }
    while(!Q.empty()) {
        int i = Q.front().F;
        int lr = Q.front().S;
        Q.pop();
        if(lr == 0) { // l
            deg_r[R[i]]--;
            if(deg_r[R[i]] == 1) {
                while(!at_r[R[i]].empty() && visited[at_r[R[i]].back()])
                    at_r[R[i]].pop_back();
                assert(!at_r[R[i]].empty());
                int j = at_r[R[i]].back();
                Q.push({j, 1});
                visited[j] = true;
                deg_r[R[j]]--;
                diff0 -= S[j];
            }
        }
        else { // r
            deg_l[L[i]]--;
            if(deg_l[L[i]] == 1) {
                while(!at_l[L[i]].empty() && visited[at_l[L[i]].back()])
                    at_l[L[i]].pop_back();
                assert(!at_l[L[i]].empty());
                int j = at_l[L[i]].back();
                Q.push({j, 0});
                visited[j] = true;
                deg_l[L[j]]--;
                diff0 += S[j];
            }
        }
    }
//    printf("diff0: %d\nvisited\n", diff0);
//    for(int j = 0; j < 2*n; j++) {
//        printf("%d ", visited[j]);
//    }
//    printf("\n");
    vector<int> v;
    for(int i = 0; i < n; i++) {
//        printf("i = %d\nvisited:\n", i);
//        for(int j = 0; j < 2*n; j++) {
//            printf("%d ", visited[j]);
//        }
//        printf("\n");
        if(deg_l[i] > 2) impossible("a");
        if(deg_r[i] > 2) impossible("b");
        assert(deg_l[i] != 1);
        assert(deg_r[i] != 1);
        if(deg_l[i] == 2) {
            while(!at_l[i].empty() && visited[at_l[i].back()])
                at_l[i].pop_back();
            int j = at_l[i].back();
            int sum = 0;
            diff0 += S[j];
            sum -= S[j];
            deg_l[i]--;
            visited[j] = true;
            //printf("push %d (%d)\n", j, 0);
            Q.push({j, 0});
            while(!Q.empty()) {
                int a = Q.front().F;
                int lr = Q.front().S;
                Q.pop();
//                printf("a = %d\nvisited:\n", a);
//                for(int x = 0; x < 2*n; x++) {
//                    printf("%d ", visited[x]);
//                }
//                printf("\n");
                if(lr == 0) { // l
                    deg_r[R[a]]--;
                    if(deg_r[R[a]] != 1) impossible("c");
                    while(!at_r[R[a]].empty() && visited[at_r[R[a]].back()])
                        at_r[R[a]].pop_back();
                    assert(!at_r[R[a]].empty());
                    int b = at_r[R[a]].back();
                    //printf("push %d (%d)\n", b, 1);
                    Q.push({b, 1});
                    visited[b] = true;
                    deg_r[R[b]]--;
                    diff0 -= S[b];
                    sum += S[b];
                }
                else { // r
                    deg_l[L[a]]--;
                    if(deg_l[L[a]] == 0 && L[a] == i) continue;
                    if(deg_l[L[a]] != 1) impossible("d");
                    while(!at_l[L[a]].empty() && visited[at_l[L[a]].back()])
                        at_l[L[a]].pop_back();
                    assert(!at_l[L[a]].empty());
                    int b = at_l[L[a]].back();
                    //printf("push %d (%d)\n", b, 0);
                    Q.push({b, 0});
                    visited[b] = true;
                    deg_l[L[b]]--;
                    diff0 += S[b];
                    sum -= S[b];
                }
            }
            v.PB(2*sum);
        }
        if(deg_r[i] == 2) {
            while(!at_r[i].empty() && visited[at_r[i].back()])
                at_r[i].pop_back();
            int j = at_r[i].back();
            int sum = 0;
            diff0 -= S[j];
            sum += S[j];
            deg_r[i]--;
            visited[j] = true;
            Q.push({j, 1});
            while(!Q.empty()) {
                int a = Q.front().F;
                int lr = Q.front().S;
                Q.pop();
                if(lr == 0) { // l
                    deg_r[R[a]]--;
                    if(deg_r[R[a]] == 0 && R[a] == i) continue;
                    if(deg_r[R[a]] != 1) impossible("e");
                    while(!at_r[R[a]].empty() && visited[at_r[R[a]].back()])
                        at_r[R[a]].pop_back();
                    assert(!at_r[R[a]].empty());
                    int b = at_r[R[a]].back();
                    Q.push({b, 1});
                    visited[b] = true;
                    deg_r[R[b]]--;
                    diff0 -= S[b];
                    sum += S[b];
                }
                else { // r
                    deg_l[L[a]]--;
                    if(deg_l[L[a]] != 1) impossible("f");
                    while(!at_l[L[a]].empty() && visited[at_l[L[a]].back()])
                        at_l[L[a]].pop_back();
                    assert(!at_l[L[a]].empty());
                    int b = at_l[L[a]].back();
                    Q.push({b, 0});
                    visited[b] = true;
                    deg_l[L[b]]--;
                    diff0 += S[b];
                    sum -= S[b];
                }
            }
            v.PB(2*sum);
        }
    }
//    cerr << diff0 << "\n";
//    for(int x : v) {
//        cerr << x << " ";
//    }
//    cerr << "\n";
    sort(all(v));
    multiset<int> MS(all(v));
    for(int x = *MS.begin(); x <= *MS.rbegin();) {
        if(MS.count(x) > 1) {
            MS.erase(MS.find(x));
            MS.erase(MS.find(x));
            MS.insert(2*x);
        }
        else {
            x++;
        }
    }
    bitset<40*MXN> poss;
    poss[20*MXN+diff0] = 1;
    for(int x : MS) {
        if(x >= 0) poss = poss | (poss << x);
        else poss = poss | (poss >> (-x));
    }
    bool ok = false;
    for(int i = 0; i < 40*MXN; i++) {
//        if(poss[i]) {
//            cerr << i-20*MXN << " ";
//        }
        if(abs(i-20*MXN) <= k && poss[i]) {
            ok = true;
        }
    }
//    cerr << "\n";
    cout << (ok ? "YES\n" : "NO\n");
    return 0;
}

/*
3 0
1 1 1
2 1 1
2 2 1
3 2 1
3 3 1
3 3 1
nah this problem suuuuucks

*/

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