Submission #1149267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149267		12345678	Tug of War (BOI15_tug)	C++20	0 / 100	161 ms	5872 KiB

tug

#include <bits/stdc++.h>

using namespace std;

const int nx=6e4+5, kx=6e5+5;

int n, k, l[nx], r[nx], s[nx], vs[nx], f, dif, tmp, v[nx], cnt, res=1e9;
set<int> deg[nx];
bitset<kx> dp[2];

void solve(int x, int idx)
{
    if (l[x]==idx)
    {
        dif+=s[x];
        deg[r[x]].erase(idx);
        if (deg[r[x]].empty()) f=1;
        else if (deg[r[x]].size()==1) solve(*deg[r[x]].begin(), r[x]);
    }
    else
    {
        dif-=s[x];
        deg[l[x]].erase(idx);
        if (deg[l[x]].empty()) f=1;
        else if (deg[l[x]].size()==1) solve(*deg[l[x]].begin(), l[x]);
    }
}

void dfs(int u, int p, int t)
{
    if (t==0)
    {
        if (vs[u]) return;
        vs[u]=1;
        if (l[u]!=p) tmp+=s[u], dfs(l[u], u, 1);
        else tmp-=s[u], dfs(r[u], u, 1);
    }
    else
    {
        if (*deg[u].begin()==p) dfs(*next(deg[u].begin()), u, 0);
        else dfs(*deg[u].begin(), u, 0);
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=2*n; i++) cin>>l[i]>>r[i]>>s[i], r[i]+=n, deg[l[i]].insert(i), deg[r[i]].insert(i);
    for (int i=1; i<=2*n; i++) if (deg[i].empty()) return cout<<"NO", 0;
    for (int i=1; i<=2*n; i++) if (deg[i].size()==1&&!f) solve(*deg[i].begin(), i);
    if (f) return cout<<"NO", 0;
    for (int i=1; i<=2*n; i++)
    {
        if (!vs[i]&&deg[i].size()==2)
        {
            tmp=0;
            dfs(i, -1, 0);
            if (tmp!=0) cout<<1/0;
            v[++cnt]=tmp;
        }
    }
    dp[0][300000]=1;
    for (int i=1; i<=cnt; i++)
    {
        int cur=i%2, pv=1-cur;
        dp[cur]=(dp[pv]>>abs(v[i]))|(dp[pv]<<abs(v[i]));
        //cout<<"tmp "<<i<<' '<<v[i]<<'\n';
        //for (int j=-10; j<=10; j++) cout<<dp[cur][300000+j]<<' ';
        //cout<<'\n';
    }
    for (int i=0; i<kx; i++) if (dp[cnt%2][i]) res=min(res, abs(dif+(300000-i)));
    //cout<<"here "<<res<<'\n';
    if (res<=k) cout<<"YES";
    else cout<<"NO";

}

/*
2 20
1 1 1
1 2 4
2 2 1
2 1 4

*/

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:59:32: warning: division by zero [-Wdiv-by-zero]
   59 |             if (tmp!=0) cout<<1/0;
      |                               ~^~

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