oj.uz

Submission #871794

# Submission time Handle Problem Language Result Execution time Memory
871794 2023-11-11T15:35:27 Z 1075508020060209tc Tug of War (BOI15_tug) C++14
0 / 100
 298 ms 30044 KB 
#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);
}
}

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];
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";

}

Compilation message

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:94: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]
   94 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
tug.cpp:103: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]
  103 |             for(int j=0;j<e[v].size();j++){
      |                         ~^~~~~~~~~~~~
tug.cpp:150: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]
  150 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 7 ms 24956 KB Output is correct
4 Correct 6 ms 25000 KB Output is correct
5 Correct 6 ms 25176 KB Output is correct
6 Correct 6 ms 25080 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25016 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 7 ms 25180 KB Output is correct
15 Correct 6 ms 25180 KB Output is correct
16 Correct 7 ms 25180 KB Output is correct
17 Correct 6 ms 25180 KB Output is correct
18 Correct 6 ms 25084 KB Output is correct
19 Correct 6 ms 25180 KB Output is correct
20 Correct 6 ms 25180 KB Output is correct
21 Correct 5 ms 20828 KB Output is correct
22 Incorrect 7 ms 29020 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 7 ms 24956 KB Output is correct
4 Correct 6 ms 25000 KB Output is correct
5 Correct 6 ms 25176 KB Output is correct
6 Correct 6 ms 25080 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25016 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 7 ms 25180 KB Output is correct
15 Correct 6 ms 25180 KB Output is correct
16 Correct 7 ms 25180 KB Output is correct
17 Correct 6 ms 25180 KB Output is correct
18 Correct 6 ms 25084 KB Output is correct
19 Correct 6 ms 25180 KB Output is correct
20 Correct 6 ms 25180 KB Output is correct
21 Correct 5 ms 20828 KB Output is correct
22 Incorrect 7 ms 29020 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 26456 KB Output is correct
2 Correct 16 ms 21592 KB Output is correct
3 Correct 269 ms 26460 KB Output is correct
4 Correct 16 ms 21596 KB Output is correct
5 Correct 267 ms 26460 KB Output is correct
6 Correct 16 ms 21592 KB Output is correct
7 Correct 266 ms 26460 KB Output is correct
8 Correct 16 ms 21596 KB Output is correct
9 Correct 270 ms 26456 KB Output is correct
10 Correct 16 ms 21596 KB Output is correct
11 Correct 264 ms 26548 KB Output is correct
12 Correct 16 ms 21596 KB Output is correct
13 Correct 273 ms 26460 KB Output is correct
14 Correct 275 ms 26460 KB Output is correct
15 Correct 16 ms 21476 KB Output is correct
16 Correct 282 ms 26456 KB Output is correct
17 Correct 20 ms 21592 KB Output is correct
18 Correct 285 ms 26512 KB Output is correct
19 Correct 16 ms 21592 KB Output is correct
20 Correct 265 ms 26472 KB Output is correct
21 Correct 16 ms 21596 KB Output is correct
22 Incorrect 18 ms 30044 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25176 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 7 ms 24956 KB Output is correct
4 Correct 6 ms 25000 KB Output is correct
5 Correct 6 ms 25176 KB Output is correct
6 Correct 6 ms 25080 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25016 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 7 ms 25180 KB Output is correct
15 Correct 6 ms 25180 KB Output is correct
16 Correct 7 ms 25180 KB Output is correct
17 Correct 6 ms 25180 KB Output is correct
18 Correct 6 ms 25084 KB Output is correct
19 Correct 6 ms 25180 KB Output is correct
20 Correct 6 ms 25180 KB Output is correct
21 Correct 5 ms 20828 KB Output is correct
22 Incorrect 7 ms 29020 KB Output isn't correct
23 Halted 0 ms 0 KB -