Submission #1020743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020743		owoovo	Tug of War (BOI15_tug)	C++17	100 / 100	1765 ms	6664 KiB

tug

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,avx2")
#define ll long long
#define F first 
#define S second 
using namespace std;
bitset<1200010> bs;
int n,k,sum,d[60010],use[60010],useedge[60010];
vector<pair<pair<int,int>,int>> edge;
vector<int> e[60010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    bs[0]=1;
    cin>>n>>k;
    for(int i=0;i<2*n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        sum+=c;
        edge.push_back({{a,b+n},c});
        e[a].push_back(i);
        e[b+n].push_back(i);
        d[a]++;
        d[b+n]++;
    }
    queue<int> q;
    for(int i=1;i<=2*n;i++){
        if(d[i]==1)q.push(i);
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto x:e[now]){
            if(useedge[x]!=0)continue;
            useedge[x]=1;
            if(now<=n){
                bs<<=edge[x].S;
            }
            use[now]=1;
            d[edge[x].F.F]--;
            if(d[edge[x].F.F]==1)q.push(edge[x].F.F);
            d[edge[x].F.S]--;
            if(d[edge[x].F.S]==1)q.push(edge[x].F.S);
        }
    }
    for(int i=1;i<=2*n;i++){
        if(use[i]==0&&d[i]==0){
            cout<<"NO\n";
            return 0;
        }
    }
    for(int i=1;i<=2*n;i++){
        if(use[i]==1)continue;
        ll val[2]={0,0},bt=0,cnt=0;
        int now=i;
        while(use[now]==0){
            for(auto x:e[now]){
                if(useedge[x])continue;
                useedge[x]=1;
                use[now]=1;
                val[bt]+=edge[x].S;
                bt^=1;
                now=now^edge[x].F.F^edge[x].F.S;
                break;
            }
        }
        bs=(bs<<val[0])|(bs<<val[1]);
    }
    for(int i=0;i<=sum;i++){
        if(abs(sum-2*i)<=k&bs[i]){
            cout<<"YES\n";
            return 0;
        }
    }
    cout<<"NO\n";
    return 0;
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:55:30: warning: unused variable 'cnt' [-Wunused-variable]
   55 |         ll val[2]={0,0},bt=0,cnt=0;
      |                              ^~~
tug.cpp:71:24: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   71 |         if(abs(sum-2*i)<=k&bs[i]){
      |            ~~~~~~~~~~~~^~~

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