제출 #1199617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199617		Ludissey	Tug of War (BOI15_tug)	C++20	23 / 100	10 ms	5196 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(sm);
        }
    }
    sort(all(a));
    vector<int> pref(n,a[0]);
    for (int i = 1; i < sz(a); i++) pref[i]=pref[i-1]+a[i];
    
    for (int i = 0; i <= sz(a); i++)
    {
        for (int j = i; j <= sz(a); j++)
        {
            int sm=pref[sz(a)-1];
            if(i>0) sm+=pref[i-1]*2;
            if(j<n) sm-=pref[j]*2;
            if(abs(sm+sum)<=k||abs(-sm+sum)<=k){
                cout << "YES\n";
                return 0;
            }
        }
    }

    cout << "NO\n";
    return 0;
}

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