Submission #86079

#	Time	Username	Problem	Language	Result	Execution time	Memory
86079		Flying_dragon_02	Tug of War (BOI15_tug)	C++14	0 / 100	66 ms	21580 KiB

tug

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 60005;

void bye() {
    cout << "NO";
    exit(0);
}

int n, lmao;

int l[N], r[N], s[N], sum, incycle[N], par[N], used[20 * N], dp[2][20 * N], total;

vector<int> graph[3 * N];

bool vis[3 * N];

vector<int> can;

vector<vector<int>> vec;

void bfs(int u, int p) {
    vis[u] = 1;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(v == p) continue;
        if(vis[v]) {
            if(incycle[v]) continue;
            vector<int> temp;
            int z = u;
            while(z != v) {
                incycle[z] = 1;
                temp.pb(z);
                z = par[z];
            }
            incycle[v] = 1;
            temp.pb(v);
            vec.pb(temp);
            continue;
        }
        par[v] = u;
        bfs(v, u);
    }
}

void check() {
    for(int i = 2 * n + 1; i <= 4 * n; i++) {
        if(graph[i].size() >= 3)
            bye();
    }
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n >> lmao;
    for(int i = 1; i <= 2 * n; i++) {
        cin >> l[i] >> r[i] >> s[i];
        total += s[i];
        graph[i].pb(2 * n + l[i]);
        graph[2 * n + l[i]].pb(i);
        graph[i].pb(3 * n + r[i]);
        graph[3 * n + r[i]].pb(i);
    }
    check();
    for(int i = 1; i <= 4 * n; i++) {
        if(!vis[i])
            bfs(i, i);
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 2 * n + 1; i <= 4 * n; i++) {
        if(incycle[i] == 0 && vis[i] == 0 && graph[i].size() == 1) {
            int z = i;
            while(incycle[z] == 0 && vis[z] == 0) {
                vis[z] = 1;
                if(z >= 2 * n + 1 && z <= 3 * n)
                    sum += s[par[z]];
                z = par[z];
            }
        }
    }
    for(int i = 0; i < vec.size(); i++) {
        vector<int> temp = vec[i];
        int sum1 = 0, sum2 = 0, m = temp.size();
        for(int j = 0; j < m; j++) {
            if(temp[j] <= 2 * n && temp[(j + 1) % m] >= 2 * n + 1 && temp[(j + 1) % m] <= 3 * n)
                sum1 += s[temp[j]];
        }
        for(int j = 0; j < m; j++) {
            if(temp[j] <= 2 * n && temp[(j - 1 + m) % m] >= 2 * n + 1 && temp[(j - 1 + m) % m] <= 3 * n)
                sum2 += s[temp[j]];
        }
        sum += min(sum1, sum2);
        sum1 -= min(sum1, sum2); sum2 -= min(sum1, sum2);
        if(max(sum1, sum2) == 0) continue;
        if(used[max(sum1, sum2)] == 0)
            can.pb(max(sum1, sum2));
        used[max(sum1, sum2)]++;
    }
    sort(can.begin(), can.end());
    int lol = can.size();
    for(int i = 0; i <= 1; i++) {
        for(int j = 0; j < 20 * N; j++)
            dp[i][j] = 20 * N;
    }
    dp[0][0] = 0;
    for(int i = 0; i < lol; i++) {
        for(int j = 0; j < 20 * N; j++) {
            if(dp[0][j] > used[can[i]]) continue;
            dp[1][j] = 0;
            if(dp[0][j] < used[can[i]])
                dp[1][j + can[i]] = min(dp[1][j + can[i]], dp[0][j] + 1);
        }
        for(int j = 0; j < 20 * N; j++) {
            dp[0][j] = dp[1][j];
            dp[1][j] = 20 * N;
        }
    }
    for(int i = 0; i < 20 * N; i++) {
        if(dp[0][i] < 20 * N) {
            int temp = i + sum;
            int lef = total - temp;
            if(abs(lef - temp) <= lmao) {
                cout << "YES";
                exit(0);
            }
        }
    }
    bye();
}

Compilation message (stderr)

tug.cpp: In function 'void bfs(int, int)':
tug.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); i++) {
                    ~~^~~~~~~~~~~~

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