Submission #940161

#	Time	Username	Problem	Language	Result	Execution time	Memory
940161		irmuun	Tug of War (BOI15_tug)	C++17	71 / 100	3042 ms	12076 KiB

tug

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int>l(2*n),r(2*n),s(2*n);
    set<int>v[2*n];
    for(int i=0;i<2*n;i++){
        cin>>l[i]>>r[i]>>s[i];
        l[i]--;
        r[i]--;
        r[i]+=n;
        v[l[i]].insert(i);
        v[r[i]].insert(i);
    }
    queue<int>q;
    bool ok=true;
    for(int i=0;i<2*n;i++){
        if(v[i].size()==0){
            cout<<"NO";
            return 0;
        }
        if(v[i].size()==1){
            q.push(i);
        }
    }
    vector<int>w(2*n,-1);
    vector<bool>used(2*n,0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(v[x].size()==0) continue;
        int y=*v[x].begin();
        used[y]=true;
        w[x]=s[y];
        v[l[y]].erase(y);
        v[r[y]].erase(y);
        if(v[l[y]].size()==1){
            q.push(l[y]);
        }
        if(v[r[y]].size()==1){
            q.push(r[y]);
        }
    }
    vector<int>adj[2*n];
    vector<int>num;
    function <void(int)> dfs=[&](int x){
        if(used[x]==true) return;
        num.pb(s[x]);
        used[x]=true;
        for(int y:adj[x]){
            dfs(y);
        }
    };
    for(int i=0;i<2*n;i++){
        if(w[i]==-1){
            int x=*v[i].begin();
            v[i].erase(v[i].begin());
            int y=*v[i].begin();
            v[i].erase(y);
            adj[x].pb(y);
            adj[y].pb(x);
        }
    }
    vector<int>dif;
    for(int i=0;i<2*n;i++){
        num.clear();
        dfs(i);
        if(!num.empty()){
            int cur=0;
            for(int j=0;j<(int)num.size();j++){
                if(j%2==0) cur+=num[j];
                else cur-=num[j];
            }
            dif.pb(abs(cur));
        }
    }
    int cur=0;
    for(int i=0;i<n;i++){
        if(w[i]>-1) cur+=w[i];
    }
    for(int i=n;i<2*n;i++){
        if(w[i]>-1) cur-=w[i];
    }
    dif.pb(abs(cur));
    sort(all(dif));
    vector<bool>can(20*n,0);
    int tot=0;
    can[0]=true;
    for(int x:dif){
        for(int j=tot;j>=0;j--){
            can[j+x]=(can[j]|can[j+x]);
        }
        can[x]=true;
        tot+=x;
    }
    int mn=1e9;
    for(int i=0;i<=20*n;i++){
        if(can[i]){
            mn=min(mn,abs(tot-2*i));
        }
    }
    if(mn<=k){
        cout<<"YES";
    }
    else{
        cout<<"NO";
    }
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:27:10: warning: unused variable 'ok' [-Wunused-variable]
   27 |     bool ok=true;
      |          ^~

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