Submission #93175

#	Time	Username	Problem	Language	Result	Execution time	Memory
93175		popovicirobert	Tug of War (BOI15_tug)	C++14	100 / 100	485 ms	9080 KiB

tug

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXVAL = 300000;
const int MAXN = 30000;

vector < pair <int, int> > g[4 * MAXN + 1];

bool vis[4 * MAXN + 1];
queue <int> Q;
int n;

void dfs(int nod, int &cur) {
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it.first] == 0) {
            if(it.first > 2 * n) {
                if(it.first <= 3 * n) {
                    cur += it.second;
                }
                else {
                    cur -= it.second;
                }
            }
            dfs(it.first, cur);
        }
    }
}

int deg[4 * MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for(i = 1; i <= 2 * n; i++) {
        int l, r, s;
        cin >> l >> r >> s;
        l += 2 * n;
        r += 3 * n;
        g[i].push_back({l, s});
        g[l].push_back({i, s});
        g[i].push_back({r, s});
        g[r].push_back({i, s});
    }
    for(i = 2 * n + 1; i <= 4 * n; i++) {
        if(g[i].size() == 1) {
            Q.push(i);
            vis[i] = 1;
        }
    }
    int sl = 0, sr = 0;
    while(Q.size()) {
        int nod = Q.front();
        Q.pop();
        for(auto it : g[nod]) {
            if(vis[it.first] == 0) {
                if(it.first <= 2 * n) {
                    vis[it.first] = 1;
                    Q.push(it.first);
                    if(nod <= 3 * n) {
                        sl += it.second;
                    }
                    else {
                        sr += it.second;
                    }
                    for(auto itr : g[it.first]) {
                        deg[itr.first]++;
                    }
                }
                else if(deg[it.first] + 1 == g[it.first].size()) {
                    vis[it.first] = 1;
                    Q.push(it.first);
                }
            }
        }
    }
    //cerr << sl << " " << sr << "\n";
    bitset < MAXVAL + 1 > bs;
    bs[0] = 1;
    int tot = 0;
    for(i = 1; i <= 2 * n; i++) {
        if(vis[i] == 0) {
            int cur = 0;
            dfs(i, cur);
            cur = abs(cur);
            tot += cur;
            bs |= (bs << cur);
            //cerr << cur << "\n";
        }
    }
    for(i = 1; i <= 4 * n; i++) {
        if(vis[i] == 0) {
            cout << "NO";
            return 0;
        }
    }
    for(i = 0; i <= MAXVAL; i++) {
        if(abs(sl - sr + tot - 2 * i) <= k && bs[i]) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:81:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 else if(deg[it.first] + 1 == g[it.first].size()) {
                         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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