제출 #940160

#제출 시각아이디문제언어결과실행 시간메모리
940160irmuunTug of War (BOI15_tug)C++17
23 / 100
16 ms4480 KiB
#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=0;j<=tot;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"; } }

컴파일 시 표준 에러 (stderr) 메시지

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