Submission #1210787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210787		quocbaoo	Tug of War (BOI15_tug)	C++20	0 / 100	334 ms	5840 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;int A=0,B=0;
void dfs0(int i){
    if (g[i].size()==0) return;
    kt[i]=true;
    int nx=(*g[i].begin()).fi,co=(*g[i].begin()).se;
    if (i<=n) A+=co;else B+=co; 
    if (g[nx].size()>0) g[nx].erase(g[nx].find({i,co}));
    g[i].clear() ;   
    dfs0(nx);
}
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];
        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()==1){
            dfs0(i);
        }
        if (g[i].size()==0&&kt[i]==false) {
            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:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("peri.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
tug.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("peri.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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