답안 #559385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559385	2022-05-09T17:08:30 Z	Olympia	Tug of War (BOI15_tug)	C++17	0 / 100	53 ms	3700 KB

tug

#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> > > adj;
vector<bool> hasVisited;
int ans = 0;
void dfs (int curNode, int prevNode) {
    if (hasVisited[curNode]) {
        return;
    }
    hasVisited[curNode] = true;
    for (pair<int,int> p: adj[curNode]) {
        if (p.first != prevNode) {
            ans += p.second;
            dfs (p.first, curNode);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    adj.resize(2 * n);
    hasVisited.assign(2 * n, false);
    map<pair<int,int>,vector<int> > myMap;
    for (int i = 0; i < 2 * n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        v += n;
        myMap[make_pair(u, v)].push_back(w);
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, -w));
    }
    vector<int> tot;
    for (int i = 0; i < n; i++) {
        if (!hasVisited[i]) {
            ans = 0;
            if (adj[i].size() != 2) {
                cout << "NO\n";
                exit(0);
            }
            //cout << adj[i].size() << '\n';
            //assert(adj[i].size() == 2);
            dfs (i, adj[i].back().first);
            tot.push_back(abs(ans));
        }
    }
    for (auto& p: myMap) {
        if (p.second.size() <= 1) {
            continue;
        }
        int a = 0;
        for (int j = 0; j < p.second.size(); j++) {
            if (j % 2) a += p.second[j];
            else a -= p.second[j];
        }
        tot.push_back(abs(a));
    }
    bitset<60000> bs;
    bs.set(30000);
    for (int j: tot) {
        bs = (bs >> j) | (bs << j);
    }
    for (int i = 0; i <= k; i++) {
        if (bs[30000 + i]) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
}

Compilation message

tug.cpp: In function 'int main()':
tug.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int j = 0; j < p.second.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~

Subtask #1

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	2656 KB	Output is correct
2	Correct	14 ms	3640 KB	Output is correct
3	Correct	45 ms	2672 KB	Output is correct
4	Correct	18 ms	3700 KB	Output is correct
5	Correct	53 ms	2644 KB	Output is correct
6	Correct	15 ms	3668 KB	Output is correct
7	Correct	49 ms	2680 KB	Output is correct
8	Correct	13 ms	3592 KB	Output is correct
9	Correct	43 ms	2748 KB	Output is correct
10	Correct	13 ms	3668 KB	Output is correct
11	Correct	44 ms	2744 KB	Output is correct
12	Correct	14 ms	3668 KB	Output is correct
13	Correct	44 ms	2644 KB	Output is correct
14	Correct	51 ms	2756 KB	Output is correct
15	Correct	16 ms	3668 KB	Output is correct
16	Correct	48 ms	2684 KB	Output is correct
17	Correct	13 ms	3592 KB	Output is correct
18	Correct	51 ms	2696 KB	Output is correct
19	Correct	12 ms	3668 KB	Output is correct
20	Correct	45 ms	2744 KB	Output is correct
21	Correct	13 ms	3548 KB	Output is correct
22	Incorrect	12 ms	3116 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Incorrect	1 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-