Submission #1149567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149567		12345678	Tug of War (BOI15_tug)	C++20	100 / 100	919 ms	10296 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, tst;
set<int> deg[nx];
bitset<kx> dp[2];

void solve(int x, int idx)
{
    deg[idx].erase(x);
    if (idx<=n)
    {
        dif+=s[x];
        deg[r[x]].erase(x);
        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(x);
        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)
{
    //cout<<"dfs "<<t<<' '<<u<<' '<<p<<'\n';
    if (t==0)
    {
        //cout<<"val "<<u<<' '<<l[u]<<' '<<r[u]<<'\n';
        if (l[u]!=p) dfs(l[u], u, 1);
        else dfs(r[u], u, 1);
    }
    else
    {
        if (vs[u]) return;
        vs[u]=1;
        //cout<<"here "<<deg[u].size()<<'\n';
        if (*deg[u].begin()==p) 
        {
            if (u<=n) tmp+=s[*(next(deg[u].begin()))];
            else tmp-=s[*(next(deg[u].begin()))];
            dfs(*next(deg[u].begin()), u, 0);
        }
        else 
        {
            if (u<=n) tmp+=s[*deg[u].begin()];
            else tmp-=s[*deg[u].begin()];
            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) 
        {
            int cur=*deg[i].begin();
            if (i==l[cur]) deg[r[cur]].erase(cur);
            else deg[l[cur]].erase(cur);
            solve(cur, i);
        }
    }
    if (f) return cout<<"NO", 0;
    //cout<<"here\n";
    //for (int i=1 ;i<=2*n; i++) cout<<deg[i].size()<<' ';
    //return 0;
    for (int i=1; i<=2*n; i++)
    {
        //cout<<"size "<<i<<' '<<deg[i].size()<<'\n';
        if (!vs[i]&&deg[i].size()==2)
        {
            tmp=0;
            dfs(i, -1, 1);
            v[++cnt]=tmp;
            //cout<<"here "<<i<<' '<<tmp<<'\n';
        }
    }
    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]));
    }
    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

*/

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