Submission #1210775

#TimeUsernameProblemLanguageResultExecution timeMemory
1210775quocbaooTug of War (BOI15_tug)C++20
0 / 100
327 ms5864 KiB
#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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...