답안 #1000816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000816	2024-06-18T09:35:46 Z	LOLOLO	Tug of War (BOI15_tug)	C++17	18 / 100	48 ms	4280 KB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e4 + 100;
set <pair <int, int>> ed[N];
bool used[N];
int st = 0;
pair <int, int> dfs(int u, int v) {
    used[u] = 1;
    if (u == st && v)
        return {0, 0};

    pair <int, int> A = {0, 0};
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        A = dfs(x.f, u);
        A.f += x.s;
        swap(A.f, A.s);
    }

    return A;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    int S = 0;
    for (int i = 1; i <= n * 2; i++) {
        int l, r, s;
        cin >> l >> r >> s;
        ed[l].insert({r + n, s});
        ed[r + n].insert({l, s});
        S += s;
    } 

    queue <int> pq;
    int sz = n * 2;
    for (int i = 1; i <= sz; i++) {
        if (sz(ed[i]) == 0) {
            cout << "NO\n";
            return 0;
        }

        if (sz(ed[i]) == 1)
            pq.push(i);
    }

    int L = 0;
    while (sz(pq)) {
        int t = pq.front();
        pq.pop();
        if (sz(ed[t]) == 0)
            continue;

        auto it = *ed[t].begin();
        int s = it.f, cost = it.s;
        pair <int, int> pat = {t, cost};

        ed[s].erase(pat);
        ed[t].clear();
        if (t <= n)
            L += cost;

        if (sz(ed[s]) == 1) {
            pq.push(s);
        }
    }

    for (int i = 1; i <= sz; i++) {
        if (sz(ed[i]) > 2) {
            cout << "NO\n";
            return 0;
        }
    }

    bitset <600001> dp;
    dp[0] = 1;

    for (int i = 1; i <= sz; i++) {
        if (sz(ed[i]) == 2 && used[i] == 0) {
            st = i;
            pair <int, int> A = dfs(i, 0);
            dp = (dp << A.f) | (dp << A.s);
        }
    }


    for (int i = 0; i <= 600000; i++) {
        if (dp[i]) {
            if (abs((S - (L + i)) - (L+ i)) <= k) {
                cout << "YES\n";
                return 0;
            }
        }
    }

    cout << "NO\n";
    return 0;
}


/*
x + s
*/

Subtask #1
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2140 KB	Output is correct
2	Correct	1 ms	2140 KB	Output is correct
3	Correct	1 ms	2168 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	3 ms	2140 KB	Output is correct
6	Correct	2 ms	2136 KB	Output is correct
7	Correct	2 ms	2236 KB	Output is correct
8	Correct	2 ms	2140 KB	Output is correct
9	Correct	1 ms	2216 KB	Output is correct
10	Correct	2 ms	2136 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	1 ms	2140 KB	Output is correct
13	Correct	2 ms	2140 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	2140 KB	Output is correct
17	Correct	1 ms	2140 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	2 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	2 ms	2248 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2140 KB	Output is correct
2	Correct	1 ms	2140 KB	Output is correct
3	Correct	1 ms	2168 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	3 ms	2140 KB	Output is correct
6	Correct	2 ms	2136 KB	Output is correct
7	Correct	2 ms	2236 KB	Output is correct
8	Correct	2 ms	2140 KB	Output is correct
9	Correct	1 ms	2216 KB	Output is correct
10	Correct	2 ms	2136 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	1 ms	2140 KB	Output is correct
13	Correct	2 ms	2140 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	2140 KB	Output is correct
17	Correct	1 ms	2140 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	2 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	2 ms	2248 KB	Output is correct
26	Correct	44 ms	2396 KB	Output is correct
27	Correct	10 ms	2648 KB	Output is correct
28	Correct	40 ms	2652 KB	Output is correct
29	Correct	10 ms	2648 KB	Output is correct
30	Correct	40 ms	2652 KB	Output is correct
31	Correct	10 ms	2608 KB	Output is correct
32	Correct	48 ms	2652 KB	Output is correct
33	Correct	10 ms	2652 KB	Output is correct
34	Correct	6 ms	2652 KB	Output is correct
35	Correct	9 ms	2664 KB	Output is correct
36	Correct	42 ms	2648 KB	Output is correct
37	Correct	10 ms	2652 KB	Output is correct
38	Correct	45 ms	2600 KB	Output is correct
39	Correct	10 ms	2652 KB	Output is correct
40	Correct	40 ms	2652 KB	Output is correct
41	Correct	11 ms	2652 KB	Output is correct
42	Correct	40 ms	2652 KB	Output is correct
43	Correct	10 ms	2652 KB	Output is correct
44	Correct	40 ms	2652 KB	Output is correct
45	Correct	10 ms	2660 KB	Output is correct
46	Correct	39 ms	2652 KB	Output is correct
47	Correct	2 ms	2396 KB	Output is correct
48	Incorrect	21 ms	2652 KB	Output isn't correct
49	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

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

Subtask #4
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2140 KB	Output is correct
2	Correct	1 ms	2140 KB	Output is correct
3	Correct	1 ms	2168 KB	Output is correct
4	Correct	1 ms	2140 KB	Output is correct
5	Correct	3 ms	2140 KB	Output is correct
6	Correct	2 ms	2136 KB	Output is correct
7	Correct	2 ms	2236 KB	Output is correct
8	Correct	2 ms	2140 KB	Output is correct
9	Correct	1 ms	2216 KB	Output is correct
10	Correct	2 ms	2136 KB	Output is correct
11	Correct	1 ms	2140 KB	Output is correct
12	Correct	1 ms	2140 KB	Output is correct
13	Correct	2 ms	2140 KB	Output is correct
14	Correct	1 ms	2140 KB	Output is correct
15	Correct	1 ms	2140 KB	Output is correct
16	Correct	1 ms	2140 KB	Output is correct
17	Correct	1 ms	2140 KB	Output is correct
18	Correct	1 ms	2136 KB	Output is correct
19	Correct	1 ms	2140 KB	Output is correct
20	Correct	1 ms	2140 KB	Output is correct
21	Correct	1 ms	2140 KB	Output is correct
22	Correct	1 ms	2140 KB	Output is correct
23	Correct	2 ms	2140 KB	Output is correct
24	Correct	1 ms	2140 KB	Output is correct
25	Correct	2 ms	2248 KB	Output is correct
26	Correct	44 ms	2396 KB	Output is correct
27	Correct	10 ms	2648 KB	Output is correct
28	Correct	40 ms	2652 KB	Output is correct
29	Correct	10 ms	2648 KB	Output is correct
30	Correct	40 ms	2652 KB	Output is correct
31	Correct	10 ms	2608 KB	Output is correct
32	Correct	48 ms	2652 KB	Output is correct
33	Correct	10 ms	2652 KB	Output is correct
34	Correct	6 ms	2652 KB	Output is correct
35	Correct	9 ms	2664 KB	Output is correct
36	Correct	42 ms	2648 KB	Output is correct
37	Correct	10 ms	2652 KB	Output is correct
38	Correct	45 ms	2600 KB	Output is correct
39	Correct	10 ms	2652 KB	Output is correct
40	Correct	40 ms	2652 KB	Output is correct
41	Correct	11 ms	2652 KB	Output is correct
42	Correct	40 ms	2652 KB	Output is correct
43	Correct	10 ms	2652 KB	Output is correct
44	Correct	40 ms	2652 KB	Output is correct
45	Correct	10 ms	2660 KB	Output is correct
46	Correct	39 ms	2652 KB	Output is correct
47	Correct	2 ms	2396 KB	Output is correct
48	Incorrect	21 ms	2652 KB	Output isn't correct
49	Halted	0 ms	0 KB	-

답안 #1000816

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 0 / 30.0

Subtask #3 0 / 23.0

Subtask #4 0 / 29.0

Subtask #1
18.0 / 18.0

Subtask #2
0 / 30.0

Subtask #3
0 / 23.0

Subtask #4
0 / 29.0