oj.uz

Submission #404467

# Submission time Handle Problem Language Result Execution time Memory
404467 2021-05-14T12:55:27 Z fvogel499 Tug of War (BOI15_tug) C++14
18 / 100
 38 ms 7436 KB 
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cassert>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define ll long long
#define rint int32_t

const int siz = 6000000/100;

bitset<siz> bit;

struct Edge {
    Edge(int lNA, int lNB, int lStrength) {
        nA = lNA;
        nB = lNB;
        strength = lStrength;
    }
    int nA, nB, strength;
};

rint main() {
    int n, tolerance;
    cin >> n >> tolerance;

    set<Edge*> graph [2*n];
    for (int i = 0; i < 2*n; i++) {
        int l, r, ls;
        cin >> l >> r >> ls;
        l--;
        r--;
        r += n;
        Edge* e = new Edge(l, r, ls);
        graph[l].insert(e);
        graph[r].insert(e);
    }

    int desequilibrium = 0;
    bool proc [2*n];
    for (int i = 0; i < 2*n; i++) proc[i] = false;
    queue<int> q;
    for (int i = 0; i < 2*n; i++) {
        if (graph[i].size() == 1) q.push(i);
    }
    while (!q.empty()) {
        int curNode = q.front();
        q.pop();
        if (proc[curNode]) continue;
        proc[curNode] = true;
        if (curNode < n) {
            desequilibrium += (*(graph[curNode].begin()))->strength; 
        }
        else {
            desequilibrium -= (*(graph[curNode].begin()))->strength;
        }
        int newNode = (*(graph[curNode].begin()))->nA;
        if (newNode == curNode) newNode = (*(graph[curNode].begin()))->nB;
        graph[newNode].erase(graph[newNode].find(*(graph[curNode].begin())));
        graph[curNode].clear();
        if (graph[newNode].size() == 1) {
            q.push(newNode);
        }
    }
    desequilibrium = max(desequilibrium, -desequilibrium);

    for (int i = 0; i < 2*n; i++) {
        if (!proc[i] and graph[i].size() == 0) {
            cout << "NO";
            return 0;
        }
        if (graph[i].size() > 2) {
            cout << "ERROR";
        }
    }

    vector<int> desequilibriums;
    desequilibriums.push_back(desequilibrium);
    int desequilibriumsSum = desequilibrium;
    for (int i = 0; i < n; i++) {
        if (proc[i]) continue;
        int locDesiquilibrium = 0;
        int curNode = i;
        int parentNode = -1;
        int step = 1;
        while (!proc[curNode]) {
            proc[curNode] = true;
            int newNode = (*(graph[curNode].begin()))->nA;
            if (newNode == curNode) newNode = (*(graph[curNode].begin()))->nB;
            if (newNode == parentNode) {
                newNode = (*(next(graph[curNode].begin())))->nA;
                if (newNode == curNode) newNode = (*(next(graph[curNode].begin())))->nB;
                locDesiquilibrium += step*(*(next(graph[curNode].begin())))->strength;
            }
            else {
                locDesiquilibrium += step*(*(graph[curNode].begin()))->strength;
            }
            if (step == 1) step = -1;
            else step = 1;
            parentNode = curNode;
            curNode = newNode;
        }
        locDesiquilibrium = max(locDesiquilibrium, -locDesiquilibrium);
        desequilibriums.push_back(locDesiquilibrium);
        desequilibriumsSum += locDesiquilibrium;
    }

    bit = bitset<siz>(0);
    bit[0] = 1;
    for (int i : desequilibriums) {
        bit |= bit<<i;
    }

    for (int i = 0; i < siz; i++) if (bit[i] and abs(i-(desequilibriumsSum-i)) <= tolerance) {
        cout << "YES";
        return 0;
    }

    cout << "NO";
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 9 ms 952 KB Output is correct
27 Correct 6 ms 972 KB Output is correct
28 Correct 9 ms 960 KB Output is correct
29 Correct 7 ms 960 KB Output is correct
30 Correct 9 ms 1060 KB Output is correct
31 Correct 7 ms 972 KB Output is correct
32 Correct 9 ms 984 KB Output is correct
33 Correct 6 ms 972 KB Output is correct
34 Correct 5 ms 1036 KB Output is correct
35 Correct 6 ms 980 KB Output is correct
36 Correct 10 ms 956 KB Output is correct
37 Correct 6 ms 972 KB Output is correct
38 Correct 9 ms 956 KB Output is correct
39 Correct 6 ms 972 KB Output is correct
40 Correct 9 ms 972 KB Output is correct
41 Correct 6 ms 972 KB Output is correct
42 Correct 10 ms 968 KB Output is correct
43 Correct 6 ms 972 KB Output is correct
44 Correct 9 ms 972 KB Output is correct
45 Correct 6 ms 956 KB Output is correct
46 Correct 9 ms 1036 KB Output is correct
47 Runtime error 6 ms 1868 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3784 KB Output is correct
2 Runtime error 28 ms 7436 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 9 ms 952 KB Output is correct
27 Correct 6 ms 972 KB Output is correct
28 Correct 9 ms 960 KB Output is correct
29 Correct 7 ms 960 KB Output is correct
30 Correct 9 ms 1060 KB Output is correct
31 Correct 7 ms 972 KB Output is correct
32 Correct 9 ms 984 KB Output is correct
33 Correct 6 ms 972 KB Output is correct
34 Correct 5 ms 1036 KB Output is correct
35 Correct 6 ms 980 KB Output is correct
36 Correct 10 ms 956 KB Output is correct
37 Correct 6 ms 972 KB Output is correct
38 Correct 9 ms 956 KB Output is correct
39 Correct 6 ms 972 KB Output is correct
40 Correct 9 ms 972 KB Output is correct
41 Correct 6 ms 972 KB Output is correct
42 Correct 10 ms 968 KB Output is correct
43 Correct 6 ms 972 KB Output is correct
44 Correct 9 ms 972 KB Output is correct
45 Correct 6 ms 956 KB Output is correct
46 Correct 9 ms 1036 KB Output is correct
47 Runtime error 6 ms 1868 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -