Submission #941507

#	Time	Username	Problem	Language	Result	Execution time	Memory
941507		Darren0724	Tug of War (BOI15_tug)	C++17	100 / 100	873 ms	6512 KiB

tug

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=60005;
const int INF=1e9;
const int M=20*30000;
int32_t main() {
    LCBorz;
    int n,k;cin>>n>>k;
    int m=n*2;
    vector<int> a(m),b(m),c(m),adj[N],deg(m+1);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        b[i]+=n;
        adj[a[i]].push_back(i);
        adj[b[i]].push_back(i);
        deg[a[i]]++;
        deg[b[i]]++;
    }
    for(int i=1;i<=m;i++){
        if(deg[i]==0){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    vector<int> vis(m);
    queue<int> q;
    int ptr=M;
    for(int i=1;i<=m;i++){
        if(deg[i]==1){
            q.push(i);
        }
    }
    while(q.size()){
        int p=q.front();
        q.pop();
        for(int j:adj[p]){
            if(vis[j])continue;
            int t=p^a[j]^b[j];
            deg[p]--;
            deg[t]--;
            if(deg[t]==0){
                cout<<"NO"<<endl;
                return 0;
            }
            vis[j]=1;
            ptr+=(p<=n?1:-1)*c[j];
            if(deg[t]==1){
                q.push(t);
            }
        }
    }
    vector<int> cyc;
    for(int i=1;i<=m;i++){
        if(deg[i]==0)continue;
        int p=i,cnt=0;
        while(1){
            int flag=0;
            for(int j:adj[p]){
                if(vis[j])continue;
                vis[j]=1;
                int t=a[j]^b[j]^p;
                deg[p]--;
                deg[t]--;
                p=t;
                cnt+=(p<=n?1:-1)*c[j];
                flag=1;
                break;
            }
            if(!flag)break;
        }
        cnt=abs(cnt);
        ptr-=cnt;
        cyc.push_back(cnt*2);
    }
    bitset<2*M+1> b1;
    b1[ptr]=1;
    for(int j:cyc){
        b1|=b1<<j;
    }
    for(int i=M-k;i<=M+k;i++){
        if(b1[i]){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
    
    
    return 0;
}

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