oj.uz

Submission #871816

# Submission time Handle Problem Language Result Execution time Memory
871816 2023-11-11T16:05:34 Z 1075508020060209tc Tug of War (BOI15_tug) C++14
0 / 100
 342 ms 31072 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;
int cnt=0;
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(tp==0){
        tota+=cr[id];
    }else{
        totb+=cr[id];
    }
    vise[id]=1;

    tp^=1;
    cnt++;
 //   if(vis[v]){continue;}
    dfs(v);
}//return;
if(cnt>=2){
    exit(cnt);
}

}

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.tie(0);
ios_base::sync_with_stdio(0);    

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;
    }
}

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;
    }
}


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[id]^br[id]^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]<<" ";
}*/

for(int i=1;i<=n+n;i++){
    if(dgr[i]==0||dgr[i]>=3){
        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(int)':
tug.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
tug.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             for(int j=0;j<e[v].size();j++){
      |                         ~^~~~~~~~~~~~
tug.cpp:167:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25944 KB Output is correct
2 Correct 5 ms 26104 KB Output is correct
3 Correct 5 ms 25956 KB Output is correct
4 Correct 5 ms 25960 KB Output is correct
5 Correct 5 ms 26116 KB Output is correct
6 Correct 5 ms 25944 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 5 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 5 ms 25948 KB Output is correct
11 Correct 6 ms 25944 KB Output is correct
12 Correct 6 ms 25948 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 5 ms 25948 KB Output is correct
15 Correct 5 ms 25948 KB Output is correct
16 Correct 5 ms 25948 KB Output is correct
17 Correct 5 ms 25948 KB Output is correct
18 Correct 5 ms 26056 KB Output is correct
19 Correct 5 ms 25948 KB Output is correct
20 Correct 5 ms 25948 KB Output is correct
21 Correct 5 ms 21852 KB Output is correct
22 Incorrect 5 ms 30072 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25944 KB Output is correct
2 Correct 5 ms 26104 KB Output is correct
3 Correct 5 ms 25956 KB Output is correct
4 Correct 5 ms 25960 KB Output is correct
5 Correct 5 ms 26116 KB Output is correct
6 Correct 5 ms 25944 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 5 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 5 ms 25948 KB Output is correct
11 Correct 6 ms 25944 KB Output is correct
12 Correct 6 ms 25948 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 5 ms 25948 KB Output is correct
15 Correct 5 ms 25948 KB Output is correct
16 Correct 5 ms 25948 KB Output is correct
17 Correct 5 ms 25948 KB Output is correct
18 Correct 5 ms 26056 KB Output is correct
19 Correct 5 ms 25948 KB Output is correct
20 Correct 5 ms 25948 KB Output is correct
21 Correct 5 ms 21852 KB Output is correct
22 Incorrect 5 ms 30072 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 27040 KB Output is correct
2 Correct 9 ms 22364 KB Output is correct
3 Correct 334 ms 27032 KB Output is correct
4 Correct 9 ms 22360 KB Output is correct
5 Correct 333 ms 27224 KB Output is correct
6 Correct 10 ms 22364 KB Output is correct
7 Correct 332 ms 27052 KB Output is correct
8 Correct 9 ms 22364 KB Output is correct
9 Correct 320 ms 26972 KB Output is correct
10 Correct 11 ms 22468 KB Output is correct
11 Correct 331 ms 27004 KB Output is correct
12 Correct 9 ms 22364 KB Output is correct
13 Correct 332 ms 27064 KB Output is correct
14 Correct 323 ms 27036 KB Output is correct
15 Correct 9 ms 22360 KB Output is correct
16 Correct 326 ms 26972 KB Output is correct
17 Correct 9 ms 22364 KB Output is correct
18 Correct 332 ms 27100 KB Output is correct
19 Correct 9 ms 22360 KB Output is correct
20 Correct 338 ms 27032 KB Output is correct
21 Correct 9 ms 22364 KB Output is correct
22 Incorrect 10 ms 31072 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25944 KB Output is correct
2 Correct 5 ms 26104 KB Output is correct
3 Correct 5 ms 25956 KB Output is correct
4 Correct 5 ms 25960 KB Output is correct
5 Correct 5 ms 26116 KB Output is correct
6 Correct 5 ms 25944 KB Output is correct
7 Correct 5 ms 25948 KB Output is correct
8 Correct 5 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 5 ms 25948 KB Output is correct
11 Correct 6 ms 25944 KB Output is correct
12 Correct 6 ms 25948 KB Output is correct
13 Correct 5 ms 25948 KB Output is correct
14 Correct 5 ms 25948 KB Output is correct
15 Correct 5 ms 25948 KB Output is correct
16 Correct 5 ms 25948 KB Output is correct
17 Correct 5 ms 25948 KB Output is correct
18 Correct 5 ms 26056 KB Output is correct
19 Correct 5 ms 25948 KB Output is correct
20 Correct 5 ms 25948 KB Output is correct
21 Correct 5 ms 21852 KB Output is correct
22 Incorrect 5 ms 30072 KB Output isn't correct
23 Halted 0 ms 0 KB -