Submission #1210772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210772		quocbaoo	Tug of War (BOI15_tug)	C++20	0 / 100	325 ms	5864 KiB

tug

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int l[60004],r[60004],s[60004],dp[60004],d[60004],p[60004];
bool kt[60004],vs[60004];
int sum=0,s1=0,s2=0;
multiset<pair<int,int>> g[60004];int n,k;
bitset<600004> pos,lu;
void dfs(int i){
    vs[i]=true;
    if (g[i].size()==0) return;
    int nx=(*g[i].begin()).fi,co=(*g[i].begin()).se;
    sum+=co;
    // cout<<i<<" "<<nx<<" "<<co<<endl;
    if (i<=n) s1+=co;else s2+=co; 
    if (g[nx].size()>0) g[nx].erase(g[nx].find({i,co}));
    g[i].clear() ;   
    dfs(nx);
}
int main(){
    if (fopen("peri.in","r")){
        freopen("peri.in","r",stdin);
        freopen("peri.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for (int i=1;i<=2*n;i++){
        cin>>l[i]>>r[i]>>s[i];
        dp[l[i]]++;dp[n+r[i]]++;
        d[l[i]]=i;p[n+r[i]]=i;
    }
    int A=0,B=0;
    for (int i=1;i<=2*n;i++){
        if (dp[i]==1) {
            if (i<=n) A+=s[d[i]],kt[d[i]]=true;else B+=s[p[i]],kt[p[i]]=true;
            // cout<<i<<" ";
        }
        if (dp[i]==0){
            cout<<"NO";return 0;
        }
    }
    for (int i=1;i<=2*n;i++){
        if (kt[i]==false){
            g[l[i]].insert({n+r[i],s[i]});
            g[n+r[i]].insert({l[i],s[i]});
        }
    }
    for (int i=1;i<=2*n;i++) if (g[i].size()>2){
        cout<<"NO";return 0;
    }
    pos[0]=1;
    for (int i=1;i<=2*n;i++){
        if (vs[i]==false){
            s1=0;s2=0;
            dfs(i);
            lu=pos;pos|=(lu<<s1);pos|=(lu<<s2);
        }      
    }
    for (int i=0;i<=sum;i++){
        if (pos[i]==1&&abs(A-B+2*i-sum)<=k){
            cout<<"YES";return 0;
        }
    }
    cout<<"NO";
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("peri.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
tug.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("peri.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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