Submission #79617

#	Time	Username	Problem	Language	Result	Execution time	Memory
79617		minhtung0404	Tug of War (BOI15_tug)	C++17	100 / 100	2879 ms	6116 KiB

tug

//https://oj.uz/problem/view/BOI15_tug

#include<bits/stdc++.h>
const int N = 30005;
using namespace std;

typedef pair <int, int> ii;
vector <ii> adj[2*N];
vector <int> mv;

int n, k, cnt[2*N], d[2*N], C[2], sum;
bool dead[2*N], dp[40*N];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;

    for (int i = 1; i <= 2*n; i++){
        int l, r, c;
        cin >> l >> r >> c;
        adj[l].push_back(ii(r+n, c)); cnt[l]++;
        adj[r+n].push_back(ii(l, c)); cnt[r+n]++;
        d[i] = -1;
    }

    queue <int> mq;
    for (int i = 1; i <= 2*n; i++) if (cnt[i] == 1) mq.push(i);

    while (mq.size()){
        int u = mq.front(); mq.pop();
        dead[u] = true;
        for (auto p : adj[u]){
            if (dead[p.first]) continue;
            cnt[p.first]--;
            C[(u <= n)] += p.second;
            if (cnt[p.first] == 1) mq.push(p.first);
        }
    }

    for (int i = 1; i <= 2*n; i++) {
        if (!dead[i]) {
            if (cnt[i] != 2) return cout << "NO", 0;
            int u = i, num = 0, ck = 1;

            for (auto p : adj[u]){
                int v = p.first, cost = p.second;
                if (dead[v]) continue;
                num = cost;
            }

            while (ck){
                dead[u] = true; ck = 0;
                for (auto p : adj[u]){
                    int v = p.first, cost = p.second;
                    if (dead[v]) continue;
                    u = v; num = cost - num; ck = 1;
                    break;
                }
            }

            mv.push_back(abs(num));
            sum -= abs(num);
        }
    }
    for (int i = 0; i < 40*N; i++) dp[i] = 0;
    sort(mv.begin(), mv.end());
    dp[0] = 1;

    int cnt = 0;
    for (; cnt < mv.size();) {
        int val = mv[cnt], num = 0;
        while (cnt < mv.size() && mv[cnt] == val) cnt++, num += val;

        for (int i = 0; i < val; i++){
            int last = -1;
            for (int j = i; j < 40*N; j += val){
                if (dp[j]) {
                    last = j;
                }
                else {
                    if (last != -1 && (j - last) <= num) dp[j] = 1;
                }
            }
        }
    }

    for (int i = 0; i < 40*N; i++){
        if (abs(C[0] - C[1] + sum + i*2) <= k && dp[i]) return cout << "YES", 0;
    }
    cout << "NO";
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (; cnt < mv.size();) {
            ~~~~^~~~~~~~~~~
tug.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (cnt < mv.size() && mv[cnt] == val) cnt++, num += val;
                ~~~~^~~~~~~~~~~

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