東京工業大学プログラミングコンテスト2019 H問題 - 救援

Source

東京工業大学プログラミングコンテスト2019
問題文

問題概要

省略

解法

省略

cLay（version 20190830-1）のコード

C++に変換後のコードはこちら

int N, X[1d5], P[1d5], Q, A[1d5], B[1d5];

priority_queue< pair<int,ll> > dq[1d5], iq[1d5];
{
  int i, j, k, d, m;
  pair<int,ll> p, p1, p2;
  ll res = 0;
  unionFind uf;
  
  rd(N,(X,P)(N),Q,(A--,B--)(Q));
  uf.walloc(N);
  uf.init(N);

  rep(i,N){
    if(X[i] > 0) dq[i].push( make_pair(0,X[i]) );
    if(X[i] < 0) iq[i].push( make_pair(P[i],-X[i]) );
  }

  rep(d,Q){
    i = uf(A[d]);
    j = uf(B[d]);
    if(i==j) wt(res), continue;

    uf(i,j);
    k = uf(i);

    if(i!=k) m = i;
    if(j!=k) m = j;
    while(dq[m].size()){
      p = dq[m].top(); dq[m].pop();
      dq[k].push(p);
    }
    while(iq[m].size()){
      p = iq[m].top(); iq[m].pop();
      iq[k].push(p);
    }

    while(dq[k].size() && iq[k].size()){
      p1 = dq[k].top();
      p2 = iq[k].top();
      if( -p1.first >= p2.first ) break;
      dq[k].pop();
      iq[k].pop();
      m = min(p1.second, p2.second);
      p1.second -= m;
      p2.second -= m;
      res += (ll)m * (p1.first + p2.first);
      if(p1.second) dq[k].push(p1);
      if(p2.second) iq[k].push(p2);
      if(p2.first) dq[k].push( make_pair(-p2.first, m) );
      if(p1.first) iq[k].push( make_pair(-p1.first, m) );
    }

    while(dq[k].size() >= 2){
      p1 = dq[k].top(); dq[k].pop();
      p2 = dq[k].top(); dq[k].pop();
      if(p1.first == p2.first){
        p1.second += p2.second;
        dq[k].push(p1);
      } else {
        dq[k].push(p1);
        dq[k].push(p2);
        break;
      }
    }

    while(iq[k].size() >= 2){
      p1 = iq[k].top(); iq[k].pop();
      p2 = iq[k].top(); iq[k].pop();
      if(p1.first == p2.first){
        p1.second += p2.second;
        iq[k].push(p1);
      } else {
        iq[k].push(p1);
        iq[k].push(p2);
        break;
      }
    }

    wt(res);
  }
}

Current time: 2024年04月25日19時12分05秒
Last modified: 2019年09月01日00時50分49秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)