Submission #86088

#	Time	Username	Problem	Language	Result	Execution time	Memory
86088		Flying_dragon_02	Tug of War (BOI15_tug)	C++14	100 / 100	1228 ms	34772 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[2 * N], par[2 * N], used[20 * N], dp[2][20 * N], total, num;

vector<int> graph[2 * N];

bool vis[2 * N];

vector<int> can;

vector<vector<int>> vec;

void bfs(int u, int p, int type) {
    vis[u] = 1;
    if(u > 2 * n)
        num++;
    else
        num--;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(v == p) continue;
        if(vis[v]) {
            if(type == 1) {
                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;
        }
        if(type == 2 || type == 1)
            par[v] = u;
        bfs(v, u, type);
    }
    if(type == 3) {
        if(incycle[u] == 0 && u <= 2 * n) {
            int lmao1 = 0, v;
            for(int i = 0; i < graph[u].size(); i++) {
                if(par[graph[u][i]] == u) {
                    v = graph[u][i];
                    break;
                }
            }
            if(v <= 3 * n)
                sum += s[u];
        }
    }
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    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);
        //cout << i << " " << 2 * n + l[i] << "\n";
        //cout << i << " " << 3 * n + r[i] << "\n";
    }
    for(int i = 1; i <= 2 * n; i++) {
        if(!vis[i]) {
            bfs(i, i, 2);
            if(num != 0)
                bye();
        }
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= 2 * n; i++) {
        if(!vis[i])
            bfs(i, i, 1);
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= 2 * n; i++) {
        if(!vis[i] && incycle[i] == 1)
            bfs(i, i, 2);
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= 2 * n; i++) {
        if(!vis[i]) {
            bfs(i, i, 3);
        }
    }
    //cout << sum << "\n";
    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] <= 3 * n)
                sum1 += s[temp[j]];
        }
        for(int j = 0; j < m; j++) {
            if(temp[j] <= 2 * n && temp[(j - 1 + m) % m] <= 3 * n)
                sum2 += s[temp[j]];
        }
        sum += min(sum1, sum2);
        int y = min(sum1, sum2);
        sum1 -= y; sum2 -= y;
        if(max(sum1, sum2) == 0) continue;
        if(used[max(sum1, sum2)] == 0)
            can.pb(max(sum1, sum2));
        used[max(sum1, sum2)]++;
    }
    // << sum << "\n";
    sort(can.begin(), can.end());
    int lol = can.size();
    for(int i = 0; i <= 1; i++) {
        for(int j = 0; j < 5 * N; j++)
            dp[i][j] = 20 * N;
    }
    dp[0][0] = 0;
    for(int i = 0; i < lol; i++) {
        for(int j = 0; j < 5 * N; j++) {
            if(dp[0][j] > used[can[i]]) continue;
            dp[1][j] = 0;
            if(dp[0][j] < used[can[i]])
                dp[0][j + can[i]] = min(dp[0][j + can[i]], dp[0][j] + 1);
        }
        for(int j = 0; j < 5 * N; j++) {
            dp[0][j] = dp[1][j];
            dp[1][j] = 20 * N;
        }
    }
    //cout << "wtf\n";
    for(int i = 0; i < 5 * 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, int)':
tug.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
tug.cpp:63:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < graph[u].size(); i++) {
                            ~~^~~~~~~~~~~~~~~~~
tug.cpp:62:17: warning: unused variable 'lmao1' [-Wunused-variable]
             int lmao1 = 0, v;
                 ^~~~~
tug.cpp: In function 'int main()':
tug.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); i++) {
                    ~~^~~~~~~~~~~~
tug.cpp: In function 'void bfs(int, int, int)':
tug.cpp:69:13: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(v <= 3 * n)
             ^~

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