Submission #871497

#	Time	Username	Problem	Language	Result	Execution time	Memory
871497		1075508020060209tc	Tug of War (BOI15_tug)	C++14	0 / 100	3031 ms	32140 KiB

tug

//#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 n;int K;
vector<int>e[500005];
int ar[500005];int br[500005];int cr[500005];
int vise[500005];
int vis[500005];
int ok;
int dvis[500005];
void dfs(int nw){
dvis[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int id=e[nw][i];
    if(vise[id]){continue;}
    int v=nw^ar[id]^br[id];
    if(vis[v]){ok=0;return;}
    vise[id]=v;
    vis[v]=id;
    dfs(v);
}


}

int dp[2][600005];
vector<int>chok(int pl){
vector<int>ret;
for(int i=0;i<e[pl].size();i++){
    vise[e[pl][i]]=pl;
    vis[pl]=e[pl][i];
    ok=1;
    dfs(pl);
    int tot=0;
    for(int j=1;j<=n;j++){
        if(vis[j]){

            tot+=cr[vis[j]];
        }
    }
    if(ok){
        ret.push_back(tot);
    }
    for(int j=1;j<=n+n;j++){
        vis[j]=0;vise[j]=0;
    }
}
if(ret.size()==0){
    cout<<"NO\n";
}
return ret;
}

vector<vector<int>>var;
int tot;
signed main(){
cin>>n>>K;
for(int i=1;i<=n+n;i++){
    int a;int b;int c;
    cin>>a>>b>>c;
    e[a].push_back(i);
    e[b+n].push_back(i);
    ar[i]=a;br[i]=b+n;cr[i]=c;
    tot+=c;
}
for(int i=1;i<=n+n;i++){
    if(dvis[i]){continue;}
    var.push_back(chok(i));
}
for(int i=0;i<var[0].size();i++){
    dp[0][var[0][i]]=1;
  //  cout<<var[0][i]<<"\n";
}
/*
for(int i=0;i<=6;i++){
    cout<<dp[0][i];
}*/

for(int i=1;i<var.size();i++){

    for(int j=0;j<var[i].size();j++){
           // cout<<var[i][j]<<"f\n";
        for(int k=0;k<=n*40;k++){
            if( var[i][j]<=k&&dp[0][k-var[i][j]] ){
                dp[1][k]=1;
            }
        }
    }
    for(int k=0;k<=n*40;k++){
        dp[0][k]=dp[1][k];
        dp[1][k]=0;
    }
}
for(int i=0;i<=n*40;i++){
   // cout<<dp[0][i]<<"\n";
    if( dp[0][i]&&abs(tot-i-i)<=K){
        cout<<"YES\n";return 0;
    }
}
cout<<"NO\n";
}

Compilation message (stderr)

tug.cpp: In function 'void dfs(long long int)':
tug.cpp:18: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]
   18 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
tug.cpp: In function 'std::vector<long long int> chok(long long int)':
tug.cpp:34: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]
   34 | for(int i=0;i<e[pl].size();i++){
      |             ~^~~~~~~~~~~~~
tug.cpp: In function 'int main()':
tug.cpp:75: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]
   75 | for(int i=0;i<var[0].size();i++){
      |             ~^~~~~~~~~~~~~~
tug.cpp:84:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 | for(int i=1;i<var.size();i++){
      |             ~^~~~~~~~~~~
tug.cpp:86: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]
   86 |     for(int j=0;j<var[i].size();j++){
      |                 ~^~~~~~~~~~~~~~

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