Submission #762444

#	Time	Username	Problem	Language	Result	Execution time	Memory
762444		MilosMilutinovic	Tug of War (BOI15_tug)	C++14	100 / 100	1144 ms	18292 KiB

tug

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 4 * N;
int n, k, l[N], r[N], s[N], up[N], cur;
vector<int> who[N], cyc;
vector<pair<int, int>> g[N];
set<int> pos, idx;
bool was[N], seen[N], on_cyc[N], gg[N];
void dfs(int x) {
    if (pos.find(x) != pos.end()) {
        return;
    }
    pos.insert(x);
    for (int i : who[x]) {
        idx.insert(i);
        dfs(l[i] ^ (n + r[i]) ^ x);
    }
}
void dfs_cyc(int x, int fa) {
    if (!cyc.empty()) {
        return;
    }
    seen[x] = true;
    for (auto& p : g[x]) {
        if (fa == p.second) {
            continue;
        }
        int y = p.first;
        if (seen[y]) {
            int ver = x;
            while (ver != y) {
                cyc.push_back(ver);
                ver = up[ver];
            }
            cyc.push_back(y);
            return;
        }
        up[y] = x;
        dfs_cyc(y, p.second);
        if (!cyc.empty()) {
            return;
        }
    }
}
void Go(int x, int p) {
    if (gg[x]) return;
    gg[x] = true;
    cur += (p <= n ? s[x] : -s[x]);
    for (int i : who[p]) {
        Go(i, l[i] ^ (r[i] + n) ^ p);
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= 2 * n; i++) {
        scanf("%d%d%d", &l[i], &r[i], &s[i]);
        who[l[i]].push_back(i);
        who[n + r[i]].push_back(i);
    }
    vector<pair<int, int>> vec;
    for (int i = 1; i <= 2 * n; i++) {
        if (was[i]) {
            continue;
        }
        pos.clear();
        idx.clear();
        dfs(l[i]);
        if (pos.size() != idx.size()) {
            printf("NO\n");
            exit(0);
        }
        for (int i : idx) {
            g[l[i]].emplace_back(n + r[i], i);
            g[n + r[i]].emplace_back(l[i], i);
        }
        cyc.clear();
        dfs_cyc(l[i], -1);
        for (int i : cyc)
            on_cyc[i] = true;
        int f = -1;
        for (int i : idx) {
            if (on_cyc[l[i]] && on_cyc[n + r[i]])
                f = i;
            was[i] = true;
        }
        cur = 0;
        for (int i : idx)
            gg[i] = false;
        Go(f, l[f]);
        int fir = cur;
        cur = 0;
        for (int i : idx)
            gg[i] = false;
        Go(f, n + r[f]);
        int sec = cur;
        vec.emplace_back(fir, sec);
        //printf("%d je taj\n", f);
    }
    bitset<M> bs;
    bs[2 * N] = 1;
    for (auto& p : vec) {
        bs = (p.first >= 0 ? (bs >> p.first) : (bs << (-p.first))) | (p.second >= 0 ? (bs >> p.second) : (bs << (-p.second)));
    }
    bool ok = false;
    for (int i = 0; i <= k; i++)
        if (bs[2 * N - i] || bs[2 * N + i])
            ok = true;
    if (ok)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

/*
4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

YES

2 5
1 1 1
1 2 4
2 2 1
2 1 4

NO
*/

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d%d", &l[i], &r[i], &s[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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