Submission #986260

#	Time	Username	Problem	Language	Result	Execution time	Memory
986260		andrei_iorgulescu	Tug of War (BOI15_tug)	C++14	100 / 100	1715 ms	13784 KiB

tug

#include <bits/stdc++.h>

using namespace std;

int n,k,dif0;
multiset<pair<int,int>> g[60005];

bool viz[60005];
int vll;

void dfs(int nod,int parval)
{
    //cout << nod << ' ' << vll << endl;
    viz[nod] = true;
    for (auto it : g[nod])
    {
        if (!viz[it.first])
        {
            if (nod <= n)
                vll += it.second;
            else
                vll -= it.second;
            dfs(it.first,it.second);
            return;
        }
    }
    for (auto it : g[nod])
    {
        if (nod <= n)
            vll += it.second;
        else
            vll -= it.second;
    }
    if (nod <= n)
        vll -= parval;
    else
        vll += parval;
}

bitset<1200005> dp;///shiftat cu 600000

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 1; i <= 2 * n; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        g[x].insert({y + n,z});
        g[y + n].insert({x,z});
    }
    set<pair<int,int>> degmin;
    for (int i = 1; i <= 2 * n; i++)
    {
        degmin.insert({g[i].size(),i});
    }
    while (!degmin.empty() and (*degmin.begin()).first < 2)
    {
        pair<int,int> pr = *degmin.begin();
        degmin.erase(degmin.begin());
        if (pr.first == 0)
        {
            cout << "NO";
            return 0;
        }
        int nod = pr.second;
        int vecin = (*g[nod].begin()).first;
        int cost = (*g[nod].begin()).second;
        if (nod <= n)
            dif0 += cost;
        else
            dif0 -= cost;
        g[nod].clear();
        g[vecin].erase(g[vecin].find({nod,cost}));
        int dgg = (int)g[vecin].size() + 1;
        degmin.erase({dgg,vecin});
        degmin.insert({dgg - 1,vecin});
    }
    vector<int> noduri;
    for (auto it : degmin)
        noduri.push_back(it.second);
    vector<int> vals;
    for (auto it : noduri)
    {
        if (!viz[it])
        {
            vll = 0;
            dfs(it,0);
            vals.push_back(abs(vll));
            //cout << abs(vll) << endl;
        }
    }
    dp[dif0 + 600000] = 1;
    //cout << dif0 << endl;
    for (auto it : vals)
    {
        dp = (dp << it) | (dp >> it);

    }
    for (int i = 600000 - k; i <= 600000 + k; i++)
    {
        if (dp[i])
        {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

/**
Fac un graf bipartit cu muchie L[i] -- R[j] pentru un om cu i sau j
deg(i) = 0 => NO
deg(i) = 1 => fac muchia aia sa fie asa si o elimin din graf, impreuna cu nodul evident
daca orice deg(i) >= 2, sum(deg(i)) >= 4N dar sum(deg(i)) == 4N deci deg(i) = 2 pentru fiecare i
graful poate fi impartit in cicluri, la fiecare ciclu am doua variante

Fie D = diferenta care s-a creat pana sa ajung la graful asta din cicluri
Raspunsul pentru s[i] = 1 este clar YES, acum sa vad cand am si k si s-uri diferite
Fiecare ciclu poate sa imi genereze doua valori, a[i] si b[i] sa zicem (fie m numarul de cicluri)
dp[i][j] = pot sa fac din primele i cicluri valoarea j (M * N * 20 de stari)
M e O(N) worst case (gen, N / 2) deci tot pot avea N^2 * 10 stari
Average bitset W lol, gen acum am aprox N^2 / 6 sau cv care ar trebui sa intre oricum
**/

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