Submission #985889

#	Time	Username	Problem	Language	Result	Execution time	Memory
985889		hengliao	Tug of War (BOI15_tug)	C++17	100 / 100	2392 ms	23124 KiB

tug

#pragma GCC target("avx2,bmi,bmi2,popcnt")
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=6e4+5;
const ll MAX=600005;

ll l[mxN];
ll r[mxN];
ll s[mxN];
ll lg[mxN];
ll rg[mxN];
ll lsum=0;
ll rsum=0;
set<pll> adj[mxN][2];
vll in[mxN];
ll cnt=0;
pll val[mxN];
bool visited[mxN][2];
bool done[mxN][2];
vector<pll> stk;
ll dt;

bitset<2*MAX> dp;
bitset<2*MAX> new_dp;

ll dfs(ll cur, ll idx, ll type){
    if(visited[cur][type]){
        return 0;
    }
    ll re=s[idx];
    if(type==0) re*=-1;
    //cout<<cur<<' '<<type<<' '<<re<<'\n';
    visited[cur][type]=1;
    done[cur][type]=1;
    for(auto &[x, y]:adj[cur][type]){
        if(y==dt) continue;
        re+=dfs(x, y, (type+1)%2);
    }
    stk.pb({cur, type});
    return re;
}

ll getidx(ll a){
    return a+MAX;
}

void solve(){
    memset(lg, 0, sizeof(lg));
    memset(rg, 0, sizeof(rg));
    memset(visited, 0, sizeof(visited));
    memset(done, 0, sizeof(done));
	ll n, k;
    cin>>n>>k;
    bool good=1;
    for(ll i=0;i<2*n;i++){
        cin>>l[i]>>r[i]>>s[i];
        l[i]--; r[i]--;
        if(s[i]!=1){
            good=0;
        } 
        adj[l[i]][0].insert({r[i], i});
        adj[r[i]][1].insert({l[i], i});
    }
    set<pair<ll, pll>> st;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<2;j++){
            st.insert({adj[i][j].size(), {i, j}});
        }
    }
    while(!st.empty()){
        pair<ll, pll> tep=*st.begin(); 
        st.erase(tep);
        if(tep.F<=0){
            cout<<"NO\n";
            return;
        }
        if(tep.F>=2){
            break;
        }
        pll cur=*adj[tep.S.F][tep.S.S].begin();
        //adj[tep.S.F][tep.S.S].erase(cur);
        if(tep.S.S==0){
            lsum+=s[cur.S];
            done[tep.S.F][0]=1;
            st.erase({adj[cur.F][1].size(), {cur.F, 1}});
            adj[cur.F][1].erase({tep.S.F, cur.S});
            adj[tep.S.F][0].erase({cur.F, cur.S});
            st.insert({adj[cur.F][1].size(), {cur.F, 1}});
        }
        else{
            rsum+=s[cur.S];
            done[tep.S.F][1]=1;
            st.erase({adj[cur.F][0].size(), {cur.F, 0}});
            adj[cur.F][0].erase({tep.S.F, cur.S});
            adj[tep.S.F][1].erase({cur.F, cur.S});
            st.insert({adj[cur.F][0].size(), {cur.F, 0}});
        }
    }
    if(good){
        cout<<"YES\n";
        return;
    }
    for(ll i=0;i<n;i++){
        if(!done[i][0]){
            dt=(*adj[i][0].begin()).S;
            val[cnt].F=dfs(i, dt, 0);
            for(auto &[x, y]:stk){
                visited[x][y]=0;
            }
            stk.clear();
            val[cnt].S=dfs(r[dt], dt, 1);
            stk.clear();
            //cout<<val[cnt].F<<' '<<val[cnt].S<<'\n';
            cnt++;
        }
    }
    dp.reset();
    dp[getidx(rsum-lsum)]=1;
    for(ll i=0;i<cnt;i++){
        new_dp.reset();
        if(val[i].F>0){
            new_dp=(new_dp | (dp<<val[i].F));
        }
        else{
            new_dp=(new_dp | (dp>>(-val[i].F)));
        }
        if(val[i].S>0){
            new_dp=(new_dp | (dp<<val[i].S));
        }
        else{
            new_dp=(new_dp | (dp>>(-val[i].S)));
        } 
        dp=new_dp;
    }
    for(ll i=0;i<=k;i++){
        if(dp[getidx(i)]){
            //cout<<i<<' ';
            cout<<"YES\n";
            return;
        }
        if(dp[getidx(-i)]){
            //cout<<-i<<' ';
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	return 0;
}

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