제출 #871799

#제출 시각아이디문제언어결과실행 시간메모리
8717991075508020060209tcTug of War (BOI15_tug)C++14
41 / 100
294 ms30232 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; int cnt=0; 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; cnt++; dfs(v); } } int uf[500005]; int usz[500005]; int ues[500005]; int fin(int x){ if(uf[x]==x){return x;} uf[x]=fin(uf[x]); return uf[x]; } void mrg(int a,int b){ int pa=fin(a);int pb=fin(b); ues[pa]++; if(pa==pb){return;} usz[pa]+=usz[pb]; ues[pa]+=ues[pb]; uf[pb]=pa; } 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]==0){ cout<<"NO\n";return 0; }*/ 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]<<" "; }*/ for(int i=1;i<=n+n;i++){ uf[i]=i; usz[i]=1; ues[i]=0; } for(int i=1;i<=n+n;i++){ if(vise[i]){continue;} mrg(ar[i],br[i]); } for(int i=1;i<=n+n;i++){ if(vis[i]){continue;} if( usz[fin(i)]!=ues[fin(i)] ){ cout<<"NO\n";return 0; } } 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}); } dp[basea]=1; for(int i=0;i<vc.size();i++){ dp2=(dp<<vc[i].first); dp2=(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:27: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]
   27 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:98: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]
   98 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
tug.cpp:107: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]
  107 |             for(int j=0;j<e[v].size();j++){
      |                         ~^~~~~~~~~~~~
tug.cpp:154: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]
  154 | 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...