제출 #871787

#제출 시각아이디문제언어결과실행 시간메모리
8717871075508020060209tcTug of War (BOI15_tug)C++14
41 / 100
248 ms28764 KiB
#pragma GCC optimize ("O3") #include<bits/stdc++.h> //#include <bits/extc++.h> //using namespace __gnu_pbds; using namespace std; #define int long long #define X first #define Y second int lowbit(int x){return x&-x;} int n;int K; vector<int>e[500005]; int vis[500005]; int vise[500005]; int dgr[500005]; int ar[500005];int br[500005];int cr[500005]; int basea; int baseb; bitset<600005>dp; bitset<600005>dp2; bitset<600005>zer; int tota;int totb; int tp; void dfs(int nw){ vis[nw]=1; //cout<<nw<<"kk"<<endl; for(int i=0;i<e[nw].size();i++){ int id=e[nw][i]; if(vise[id]){continue;} if(tp==0){ tota+=cr[id]; }else{ totb+=cr[id]; } vise[id]=1; int v=nw^ar[id]^br[id]; tp^=1; dfs(v); } } signed main(){ cin>>n>>K; int ftot=0; for(int i=1;i<=n+n;i++){ int a;int b;int c; cin>>a>>b>>c; b+=n; ar[i]=a;br[i]=b;cr[i]=c; ftot+=c; dgr[a]++; dgr[b]++; e[a].push_back(i); e[b].push_back(i); } for(int i=1;i<=n+n;i++){ if(dgr[i]==0){ cout<<"NO\n";return 0; } } queue<int>q; for(int i=1;i<=n+n;i++){ if(dgr[i]==1){ q.push(i); vise[e[i][0]]=1; if( i<=n ){ basea+=cr[e[i][0]]; } vis[i]=1; } } while(q.size()){ int nw=q.front(); q.pop(); vis[nw]=1; for(int i=0;i<e[nw].size();i++){ int id=e[nw][i]; if(vise[id]){continue;} int v=ar[i]^br[i]^nw; dgr[v]--; if(dgr[v]==1){ for(int j=0;j<e[v].size();j++){ int idd=e[v][j]; if(vise[idd]){continue;} if(v<=n){ basea+=cr[idd]; } vise[idd]=1; } q.push(v); } } }/* cout<<basea<<"\n"; for(int i=1;i<=n+n;i++){ cout<<vis[i]<<" "; }cout<<endl; for(int i=1;i<=n+n;i++){ cout<<vise[i]<<" "; }*/ vector<pair<int,int>>vc; for(int i=1;i<=n;i++){ if(vis[i]){continue;} tota=0; totb=0; tp=0; dfs(i); vc.push_back({tota,totb}); // cout<<tota<<" "<<totb<<endl; } dp[basea]=1; for(int i=0;i<vc.size();i++){ dp2=dp<<vc[i].first; dp2|=dp<<vc[i].second; swap(dp,dp2); dp2=zer; } for(int i=0;i<=n*20;i++){ if(dp[i]&&(abs(ftot-i-i)<=K)){ cout<<"YES\n";return 0; } } cout<<"NO\n"; }

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

tug.cpp: In function 'void dfs(long long int)':
tug.cpp:26:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:77:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
tug.cpp:83:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int j=0;j<e[v].size();j++){
      |                         ~^~~~~~~~~~~~
tug.cpp:114:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...