Submission #1270677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270677		hypersphere	Tug of War (BOI15_tug)	C++20	100 / 100	191 ms	21176 KiB

tug

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
 
#define ll long long

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

const ll mod = 998244353;
const ll INF = 1e18;
const int INT_INF = 2e9;
 
long long binpow(long long base, long long power, long long mod) {
    if (base == 0) return 0;
    if (base == 1) return 1;
    if (power <= 0) return 1;
    long long multiplier = (power % 2 == 0 ? 1 : base) % mod;
    return (multiplier * binpow((base * base) % mod, power / 2, mod)) % mod;
}

ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

const int N = 6e4 + 10;
struct Edge{
    int from, to;
    int strength;
    int id;

    Edge(int from = 0, int to = 0, int strength = 0, int id = 0) : 
    from(from), to(to), strength(strength), id(id){

    }
};

vector<Edge> edges;
vector<Edge> adj[N];
vector<vector<int>> cycles;

bool vis[N];
bool in_cycle[N];
stack<int> s;



void find_cycle(int node, int prev_idx = -1){
    vis[node] = true;
    s.push(node);
    //cout << node << " " << prev_idx <<  "\n";

    for(Edge v : adj[node]){
        if(v.id == prev_idx) continue;

        if(vis[v.to] && !in_cycle[v.to]){
            //cout << "Found cycle\n";
            // Cycle
            vector<int> cycle;
            int par = -1;
            do{
                int t = s.top();
                cycle.push_back(t);
                par = t;
                in_cycle[t] = true;

                s.pop();
            } while(!s.empty() && par != v.to);

            cycles.push_back(cycle);
        } 
        if(!vis[v.to]) find_cycle(v.to, v.id ^ 1); // Counter edge has id of opposite polarity
    }

    if(!in_cycle[node]) s.pop();
}

int strength_A = 0;
int strength_B = 0;
int n;

void dfs2(Edge e, int prev = -1){
    if(e.from > n){
        // Then e.from is from R. This direction benefits left team
        strength_A += e.strength;
    } else strength_B += e.strength;

    for(Edge v : adj[e.to]){
        if(v.to == prev) continue;
        dfs2(v, e.to);
    }
}

void Run(){
    int diff;
    cin >> n >> diff;

    map<pair<int, int>, vector<int>> mp;
    for(int i = 0; i < 2*n; i++){
        int l, r;
        int s;

        cin >> l >> r >> s;
        r += n;

        //cout << l << " " << r << "\n";

        int m = edges.size();
        adj[l].push_back(Edge(l, r, s, m));
        adj[r].push_back(Edge(r, l, s, m + 1));

        edges.push_back(Edge(l, r, s, m));
        edges.push_back(Edge(r, l, s, m + 1));

        mp[{l, r}].push_back(s);
        mp[{r, l}].push_back(s);
    }

    for(int i = 1; i <= 2*n; i++) if(adj[i].size() == 0) { cout << "NO\n"; return; }

    for(int i = 1; i <= 2 * n; i++){
        if(vis[i]) continue;
        find_cycle(i);
    }
    
    for(int i = 1; i <= 2*n; i++){
        if(!in_cycle[i]) continue;
        for(Edge e : adj[i]){
            if(!in_cycle[e.to]){
                dfs2(e, e.from);
            }
        }
    }

    //cout << strength_A << " " << strength_B << "\n";

    vector<pair<int, int>> comp;
    for(vector<int>& cycle : cycles){
        int forward = 0;
        int backward = 0;
        int m = cycle.size();
        if(m == 2){
            int s1 = mp[{cycle[0], cycle[1]}][0];
            int s2 = mp[{cycle[0], cycle[1]}][1];

            forward = s1 - s2;
            backward = s2 - s1;

            if(forward > backward) swap(forward, backward);
            comp.push_back({forward, backward});

            continue;
        }
        // First case: i -> i + 1
        for(int i = 0; i < m; i++){
            int s = mp[{cycle[i], cycle[(i + 1) % m]}][0];

            if(cycle[i] > n){
                forward -= s;
                backward += s;
            }
            else{
                forward += s;
                backward -= s;
            }
            

        }
        if(forward > backward) swap(forward, backward);
        comp.push_back({forward, backward});
    }

    for(pair<int, int> p : comp) strength_A += p.first; // Each activation decreases target by 2*p.second
    int target = strength_B - strength_A;

    if(target > 0){
        map<int, int> cnt;
        for(pair<int, int> p : comp) cnt[2*p.second]++;
        bitset<3000000> dp;
        dp.reset();

        dp[0] = true;
        for(auto it = cnt.begin(); it != cnt.end(); it++){
            int to_take = it->second;
            int mult = 1;

            while(to_take > 0){
                int taken = min(mult, to_take);
                to_take -= taken;

                dp |= (dp << (it->first * taken));
                mult *= 2;
            }
        }
        for(int i = 0; i < 3000000; i++){
            if(!dp[i]) continue;
            if((int)abs(target - i) <= diff){
                cout << "YES\n";
                return;
            }
        }
        cout << "NO\n";
    }
    else if(target < 0){
        // There's no way to increase this 
        target = (int)abs(target);
        if(target <= diff){
            cout << "YES\n";
        } else cout << "NO\n";
    }
    else{
        // Target == 0. Already possible
        cout << "YES\n";
    }
}

int main(){
    //freopen("CIRSSTR.INP", "r", stdin);
    //freopen("CIRSSTR.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int test = 1;
    //cin >> test;

    // Measuring running time (breaks when manual input)
    //auto time_start = clock();
    while(test--) Run();
    //auto time_end = clock();

    //cerr << "Time taken: " << time_end - time_start << "\n";
}

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