Submission #1199720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199720		Ludissey	Tug of War (BOI15_tug)	C++20	100 / 100	1821 ms	15608 KiB

tug

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

vector<pair<pair<int,int>,int>> ed;
vector<bool> visit;
vector<unordered_set<int>> vc;


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,k; cin >> n >> k;
    vector<unordered_set<int>> vc(2*n);
    vector<pair<pair<int,int>,int>> ed(2*n);
    vector<bool> visit(2*n,false);
    queue<int> q;
    int sum=0;
    for (int i = 0; i < 2*n; i++)
    {
        int l,r,s; cin >> l >> r >> s; l--; r--;
        ed[i]={{l,r+n},s};
        vc[l].insert(i);
        vc[r+n].insert(i);
    }
    for (int i = 0; i < n*2; i++)
    {
        if(sz(vc[i])==0) {
            cout << "NO\n"; 
            return 0;
        }
        if(sz(vc[i])==1){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u=q.front(); q.pop();
        int j=*vc[u].begin();
        visit[j]=true;
        if(u>=n) {
            sum-=ed[j].second;
            vc[ed[j].first.first].erase(j);
            if(sz(vc[ed[j].first.first])==0) {
                cout << "NO\n"; 
                return 0;
            }else if(sz(vc[ed[j].first.first])==1){
                q.push(ed[j].first.first);
            }
        }
        else {
            sum+=ed[j].second;
            vc[ed[j].first.second].erase(j);
            if(sz(vc[ed[j].first.second])==0) {
                cout << "NO\n"; 
                return 0;
            }else if(sz(vc[ed[j].first.second])==1){
                q.push(ed[j].first.second);
            }
        }
        vc[u].clear();
    }
    vector<int> a;
    for (int i = 0; i < 2*n; i++)
    {
        if(sz(vc[i])==2){
            int sm=0;
            int j=*(vc[i].begin());
            int u=0;
            if(i<n){
                sm+=ed[j].second;
                u=ed[j].first.second;
                vc[ed[j].first.second].erase(j);
            }else{
                sm-=ed[j].second;
                u=ed[j].first.first;
                vc[ed[j].first.first].erase(j);
            }
            queue<int> q;
            vc[i].erase(j);
            while(true){
                if(sz(vc[u])==0) break;
                j=*(vc[u].begin());
                if(u<n){
                    sm+=ed[j].second;
                    u=ed[j].first.second;
                    vc[ed[j].first.second].erase(j);
                }else{
                    sm-=ed[j].second;
                    u=ed[j].first.first;
                    vc[ed[j].first.first].erase(j);
                }
            
            }
            a.push_back(abs(sm));
        }
    }
    sort(all(a));
    const int mx=3e4*20;
    bitset<2*mx> dp(0);
    dp[sum+mx]=1;
    for (int i = 0; i <= sz(a); i++)
    {
        dp=(dp<<a[i])|(dp>>a[i]);
    }
    for (int i = mx-k; i <= mx+k; i++)
    {
        if(dp[i]) {cout << "YES\n"; return 0; }
    }
    
    cout << "NO\n";
    return 0;
}

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