Submission #655164

#	Time	Username	Problem	Language	Result	Execution time	Memory
655164		ParsaS	Tug of War (BOI15_tug)	C++14	100 / 100	947 ms	6748 KiB

tug

// In the name of God
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 3e4 * 2 + 5, M = 3e4 * 17 + 5;
int n, k, l[N], r[N], s[N];

vector<int> adj[N];
int par[N], cntn, vec[N], ver[N], veci, veri;
int cnt[N][2], h[N];
bool vis[N], mark[N], vis2[N];

int _get(int i, int v) {
    return l[i] == v ? r[i] : l[i];
}
int dfs3(int v) {
    int c = adj[v].size();
    cntn++;
    vis2[v] = true;
    for (auto e : adj[v]) {
        int i = e, u = _get(e, v), w = s[e];
        if (!vis2[u])
            c += dfs3(u);
    }
    return c;
}

void dfs(int v, int p) {
    par[v] = p;
    vis[v] = true;
    for (auto e : adj[v]) {
        int i = e, u = _get(e, v), w = s[e];
        if (p == i)
            continue;
        if (!vis[u]) {
            h[u] = h[v] + 1;
            dfs(u, i);
        }
        else if (h[u] < h[v]) {
            int u2 = _get(i, v), v2 = v;
            ver[veri++] = v;
            while (v2 != u2) {
                vec[veci++] = par[v2];
                v2 = _get(par[v2], v2);
                ver[veri++] = v2;
            }
            vec[veci++] = i;
        }
    }
}

void dfs2(int v) {
    mark[v] = true;
    for (auto e : adj[v]) {
        int i = e, u = _get(i, v), w = s[e];
        if (mark[u])
            continue;
        dfs2(u);
        cnt[v][0] += cnt[u][1];
        cnt[v][1] += cnt[u][0] + w;
    }
}
bitset<M> dp;

void solve() {
    cin >> n >> k;
    int S = 0;
    int tmpp = 1;
    for (int i = 0; i < 2 * n; i++) {
        cin >> l[i] >> r[i] >> s[i];
        S += s[i];
        r[i] += n;
        adj[l[i]].pb(i);
        adj[r[i]].pb(i);
    }
    vector<pair<int, int> > V;
    for (int i = 1; i <= 2 * n; i++) {
        if (!vis[i]) {
            veci = 0, veri = 0;
            cntn = 0;
            int cnte = dfs3(i);
            if (cnte != cntn * 2) {
                cout << "NO" << '\n';
                return;
            }
            dfs(i, -1);


            for (int j = 0; j < veri; j++) {
                int u = ver[j];
                mark[u] = true;
            }
            for (int j = 0; j < veri; j++) {
                int u = ver[j];
                dfs2(u);
            }
            int sum[2] = {0, 0};
            int tmp[2] = {0, 0};
            for (int i = 0; i < veci; i++) {
                sum[i % 2] += s[vec[i]];
                tmp[0] += cnt[ver[i]][i % 2];
                tmp[1] += cnt[ver[i]][(i % 2) ^ 1];
            }
            int x = ver[0] > n;
            V.pb(make_pair(tmp[x] + sum[0], tmp[x] + sum[1]));
        }
    }
    dp[0] = true;
    for (auto [a, b] : V) {
        dp |= (dp << b) | (dp << a);
    }
    for (int i = 0; i < M; i++) {
        if (abs(2 * i - S) <= k && dp[i]) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO";
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int dfs3(int)':
tug.cpp:25:13: warning: unused variable 'i' [-Wunused-variable]
   25 |         int i = e, u = _get(e, v), w = s[e];
      |             ^
tug.cpp:25:36: warning: unused variable 'w' [-Wunused-variable]
   25 |         int i = e, u = _get(e, v), w = s[e];
      |                                    ^
tug.cpp: In function 'void dfs(int, int)':
tug.cpp:36:36: warning: unused variable 'w' [-Wunused-variable]
   36 |         int i = e, u = _get(e, v), w = s[e];
      |                                    ^
tug.cpp: In function 'void solve()':
tug.cpp:113:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |     for (auto [a, b] : V) {
      |               ^
tug.cpp:72:9: warning: unused variable 'tmpp' [-Wunused-variable]
   72 |     int tmpp = 1;
      |         ^~~~

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