Submission #230733

#	Time	Username	Problem	Language	Result	Execution time	Memory
230733		emil_physmath	Tug of War (BOI15_tug)	C++17	100 / 100	2960 ms	6520 KiB

tug

#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <vector>
#include <set>
using namespace std;
const int maxN = 30'000;
struct Jmp
{
    int to, wei;
    operator int&() { return to; }
};

vector<Jmp> jmp[2 * maxN];
Jmp par[2 * maxN];
bool used[2 * maxN], cyc[2 * maxN];

pair<int, Jmp> DFS(int v, int& nodes, int& edges)
{
    static unordered_set<int> st;
    st.insert(v);
    ++nodes;
    used[v] = true;
    pair<int, Jmp> ret = {-1, {-1, -1}};
    edges += jmp[v].size();
    for (int i = 0; i < jmp[v].size(); ++i)
    {
        Jmp to = jmp[v][i];
        if (!used[to])
        {
            par[to] = {v, to.wei};
            pair<int, Jmp> x = DFS(to, nodes, edges);
            if (x.first != -1)
                ret = x;
            if (i + 1 < jmp[v].size() && jmp[v][i + 1] == to)
                ret = {to, {v, jmp[v][i + 1].wei}};
        }
        else if (to != par[v] && st.count(to))
            ret = {v, to};
    }
    st.erase(v);
    return ret;
}
void SolveSub(int v, int p, int& ans)
{
    for (Jmp to: jmp[v])
        if (to != p && !cyc[to])
        {
            ans += to.wei * (to % 2 ? 1 : -1);
            SolveSub(to, v, ans);
        }
}
pair<int, int> Solve(int v)
{
    int nodes = 0, edges = 0;
    par[v] = {-1, -1};
    pair<int, Jmp> p = DFS(v, nodes, edges);
    edges /= 2;
    if (edges != nodes)
    {
        cout << "NO";
        exit(0);
    }
    pair<int, int> ans;
    for (int u = p.first; u != p.second; u = par[u])
    {
        ans.first += par[u].wei * (u % 2 ? 1 : -1);
        ans.second += par[u].wei * (par[u] % 2 ? 1 : -1);
    }
    ans.first += p.second.wei * (p.second % 2 ? 1 : -1);
    ans.second += p.second.wei * (p.first % 2 ? 1 : -1);
    vector<int> cycle;
    while (true)
    {
        cycle.push_back(p.first);
        if (p.first == p.second) break;
        p.first = par[p.first];
    }
    for (int u: cycle)
        cyc[u] = true;
    int ans0 = 0;
    for (int u: cycle)
        SolveSub(u, -1, ans0);
    ans.second += ans0;
    ans.first += ans0;
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < 2 * n; ++i)
    {
        int l, r, s;
        cin >> l >> r >> s;
        --l; --r;
        jmp[2 * l].push_back({2 * r + 1, s});
        jmp[2 * r + 1].push_back({2 * l, s});
#ifdef MANSON
        cout << "(" << 2 * l << ", " << 2 * r + 1 << ": " << s << ")\n";
#endif
    }
    for (int i = 0; i < 2 * n; ++i)
        sort(jmp[i].begin(), jmp[i].end());
    vector<pair<int, int>> a;
    for (int i = 0; i < 2 * n; ++i)
        if (!used[i])
        {
            a.push_back(Solve(i));
#ifdef MANSON
            cerr << a.back().first << ", " << a.back().second << '\n';
#endif
        }
    bitset<2 * 20 * maxN + 1> dp;
    dp.set(20 * n);
    for (int i = 0; i < a.size(); ++i)
    {
        int x = a[i].first, y = a[i].second;
        dp = (x > 0 ? dp << x : dp >> -x) | (y > 0 ? dp << y : dp >> -y);
    }
    int ans = 20 * n;
    for (int i = 0; i <= 2 * 20 * n; ++i)
        if (dp[i])
            ans = min(ans, abs(20 * n - i));
    cout << (ans <= k ? "YES" : "NO");
}

Compilation message (stderr)

tug.cpp: In function 'std::pair<int, Jmp> DFS(int, int&, int&)':
tug.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < jmp[v].size(); ++i)
                     ~~^~~~~~~~~~~~~~~
tug.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (i + 1 < jmp[v].size() && jmp[v][i + 1] == to)
                 ~~~~~~^~~~~~~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:119:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~

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