Submission #494899

#	Time	Username	Problem	Language	Result	Execution time	Memory
494899		fcmalkcin	Tug of War (BOI15_tug)	C++17	100 / 100	442 ms	13400 KiB

tug

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=3e5+21;
const ll mod=998244353   ;
const ll base=1e9+1000;

/// you will be the best but now you just are trash
/// goal 2/7

ll par[maxn];
ll cnt[maxn];
ll find_par(ll u)
{
    if (par[u]<0) return u;
    return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
    if (y>x) swap(x,y);
    cnt[y]+=cnt[x];
    par[y]+=par[x];
    par[x]=y;
}
vector<ll> adj[maxn];
bool dd[maxn];
ll n;
ll x[maxn];
ll y[maxn];
ll w[maxn];
ll pos;
ll cnta=0;
vector<ll> vt;
ll ed;
void dfs(ll u,ll par)
{
    ll nw=par;
    dd[u]=1;
    vt.pb(u);
    for (auto id:adj[u])
    {
        ll to=x[id]+y[id]-u;
        if (to==nw)
        {
            nw=-1;
            continue;
        }
        if (dd[to])
        {
            ed=id;
        }
        else
        {
            dfs(to,u);
        }
    }
}
void dfs1(ll u,ll par)
{
    for (auto id:adj[u])
    {
       if (id==ed) continue;
       ll to=x[id]+y[id]-u;
       if (to==par) continue;
       if (to<=n) cnta+=w[id];
       dfs1(to,u);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll k;
    cin>> n>> k;
    for (int i=1;i<=2*n;i++)
    {
        par[i]=-1;
    }
    ll all=0;
    for (int i=1;i<=2*n;i++)
    {
        cin>>x[i]>>y[i]>>w[i];
        all+=w[i];
        y[i]+=n;
        adj[x[i]].pb(i);
        adj[y[i]].pb(i);
        dsu(x[i],y[i]);
        cnt[find_par(x[i])]++;
    }
    vector<ll> vt;
    ll nw=0;
    bitset<600002> bs;
    bs[0]=1;

    for (int i=1;i<=2*n;i++)
    {
        if (i==find_par(i))
        {
            if (cnt[i]!=-par[i])
            {
                cout <<"NO";
                return 0;
            }
            cnta=0;
            ed=-1;
            dfs(i,0);
            assert(ed!=-1);
            dfs1(x[ed],0);
            ll f=cnta+w[ed];
            cnta=0;
            dfs1(y[ed],0);
            ll l=cnta;
            if (f>l) swap(l,f);

            nw+=f;
            bs|=(bs<<(l-f));
        }
    }
    for (int i=0;i<=600000;i++)
    {
        if (bs[i])
        {
            ll vala=nw+i;
            if (abs(vala-(all-vala))<=k)
            {
                cout <<"YES";
                return 0;
            }
        }
    }
    cout <<"NO";
}
/*11 1 4
2 14 10 3 15 6 1 2 9 10 9
1 9*/

Compilation message (stderr)

tug.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
      | 
tug.cpp: In function 'int main()':
tug.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tug.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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