Submission #104615

#	Time	Username	Problem	Language	Result	Execution time	Memory
104615		teomrn	Tug of War (BOI15_tug)	C++14	100 / 100	885 ms	11172 KiB

tug

#include <stdio.h>
#include <set>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
#include <iostream>
using namespace std;

const int NMAX = 60010;

namespace FindCycles {
    set <int> who_wants_me[NMAX];
    int i_want[NMAX][2];
    int power[NMAX];
    int n;
    int ans[2];
    bool choosen[NMAX];

    void make_him_choose(int id) {
        for (int c = 0; c <= 1; c++) {
            int where = i_want[id][c];
            if (who_wants_me[where].size() == 1) {
                /// eu sunt ala
//                cout << id << " m-am dus la " << where << '\n';
                choosen[id] = 1;
                ans[where > n] += power[id];
                who_wants_me[where].erase(id);

                where = i_want[id][c ^ 1];
                who_wants_me[where].erase(id);
                if (who_wants_me[where].size() == 1)
                    make_him_choose(*who_wants_me[where].begin());
            }
        }
    }

    void seek_cycles(int id, int from, int & s1, int & s2) {
        if (choosen[id])
            return;

        choosen[id] = 1;
        s1 += power[id];
        swap(s1, s2);

        int urm = i_want[id][0] + i_want[id][1] - from;
        assert(who_wants_me[urm].size() == 2);

        int nextid = *who_wants_me[urm].begin() + *who_wants_me[urm].rbegin() - id;
        seek_cycles(nextid, urm, s1, s2);
    }

    vector <pair <int, int>> solve(bool & found, int & s_left, int & s_right) {
    /// suma din stanga, suma din dreapta, perechi de genu (a, b)

        for (int i = 1; i <= 2 * n; i++) {
            who_wants_me[i_want[i][0]].insert(i);
            who_wants_me[i_want[i][1]].insert(i);
        }

        found = 1;
        for (int i = 1; i <= 2 * n; i++)
            if (!choosen[i])
                make_him_choose(i);

        for (int i = 1; i <= 2 * n; i++)
            if (who_wants_me[i].size() > 2)
                found = 0;

        if (found == 0)
            return vector <pair <int, int>> ();

        map <int, int> nr;
        vector <pair <int, int>> r;

        s_left = ans[0], s_right = ans[1];

//        for (int i = 1; i <= 2 * n; i++) {
//            cout << "tipu i vrea " << i_want[i][0] << " si " << i_want[i][1] << "   setul i are ";
//            for (auto j : who_wants_me[i])
//                cout << i << ' ';
//            cout << '\n';
//        }

        for (int i = 1; i <= 2 * n; i++) {
            if (!choosen[i]) {
                int a = 0, b = 0;
                seek_cycles(i, i_want[i][0], a, b);
                if (a < b)
                    swap(a, b);
                s_left += a, s_right += b;
                nr[2 * (a - b)]++;
                //cout << "Pot sa pun setul " << a << ' ' << b << '\n';
            }
        }

        for (auto i : nr)
            r.push_back(i);

        return r;
    }

}

bool can[600010];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);

    FindCycles::n = n;

    for (int i = 1; i <= 2 * n; i++) {
        scanf("%d%d%d", &FindCycles::i_want[i][0], &FindCycles::i_want[i][1], &FindCycles::power[i]);
        FindCycles::i_want[i][1] += n;
    }

    bool ok;
    int s_left, s_right;

    auto vec = FindCycles::solve(ok, s_left, s_right);


    if (!ok) {
        printf("NO\n");
        return 0;
    }
    if (abs(s_left - s_right) <= k) {
        printf("YES\n");
        return 0;
    }
    if (s_left < s_right) {
        printf("NO\n");
        return 0;
    }

    int smin = s_left - s_right - k;
    int smax = s_left - s_right + k;

    //cout << s_left << ' ' << s_right << ' ' << smin << ' ' << smax << '\n';

    can[0] = 1;

    for (auto ob : vec) {
        int l = ob.first, nr = ob.second;
        //cout << l << ' ' << nr << '\n';
        for (int start = 0; start < l; start++) {
            int mana = -1;
            for (int poz = start; poz <= smax; poz += l, mana--) {
                if (can[poz])
                    mana = nr;
                else if (mana >= 0)
                    can[poz] = 1;
            }
        }
    }

    ok = 0;
    for (int i = smin; i <= smax; i++)
        if (can[i])
            ok = 1;

    if (ok)
        printf("YES\n");
    else
        printf("NO\n");

    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
tug.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &FindCycles::i_want[i][0], &FindCycles::i_want[i][1], &FindCycles::power[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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