テキトーなメモ帳

テキトーなメモ帳

AOJ:1519 Room of Time and Spirit

Union-Find木を使って精神と時の部屋に入る前の戦士の初期値の相対関係を管理するのがポイントです。


どうやって戦闘力の初期値の相対関係を算出するかというと、
INコマンドが実行されるたびに、

Ao:精神と時の部屋の発生以前に、戦士Aが持っていた戦闘力(つまり初期値)
A:精神と時の部屋の発生以降に、戦士Aに対して加算された戦闘力
Bo:精神と時の部屋の発生以前に、戦士Bが持っていた戦闘力(つまり初期値)
B:精神と時の部屋の発生以降に、戦士Bに対して加算された戦闘力
Ao + A:現在の戦士Aの戦闘力
Bo + B:現在の戦士Bの戦闘力
とおいてあげて、下記のように式変形を行えばよいです。


(Bo + B) - (Ao + A) = C
Bo - Ao = C + A - B


戦闘力の初期値の相対関係が算出できたら、Union-Find木を使ってunite(A,B)します。
このとき


nodes[root_of_A].par = root_of_B
nodes[root_of_A].diff = C + A - B + (unite前の戦士B側の木のルートとの戦闘力の差分) - (unite前の戦士A側の木のルートとの戦闘力の差分)


という風に、戦闘力の初期値の差分を記録していきます。
(unite前の戦士B側の木のルートとの戦闘力の差分) - (unite前の戦士A側の木のルートとの戦闘力の差分)をもとめるのは各木のroot同士の戦闘力の差分を求めるためです。


最後に、戦士A,Bの現在の戦闘力の差分をもとめるときは、

戦士A,Bの現在の戦闘力の差分=
- 戦士Aのrootの戦士との戦闘力の初期値の差分(Union-Find木でバックトラック)
+ 戦士Bのrootの戦士との戦闘力の初期値の差分(Union-Find木でバックトラック)
- 戦士Aの精神と時の部屋発生以降に加算された戦闘力(適当な変数で保持)
+ 戦士Bの精神と時の部屋発生以降に加算された戦闘力(適当な変数で保持)

という式を解けばもとまります。

#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

int power[100001];

struct Node{
  int par;
  int diff;
  Node() : par(0),diff(0) {}
  Node(int p,int d) : par(p),diff(d) {}
};

class UnionFindTree {
private:
  Node* nodes;
public:
  UnionFindTree(int n){
    nodes = new Node[n]();
    for(int i=0;i<n;i++){
      nodes[i].par = i;
    }
  }

  ~UnionFindTree(){
    delete[] nodes;
  }

  Node find(int x){
    if(nodes[x].par == x){
      return nodes[x];
    } else {
      Node ret = find(nodes[x].par);
      return nodes[x] = Node(ret.par,ret.diff + nodes[x].diff);
    }
  }

  void unite(int x,int y,int up){
    Node rx = find(x);
    Node ry = find(y);
    if (rx.par == ry.par){
      return;
    }

    //rx.par == rx
    //ry.par == ry
    nodes[rx.par].par = ry.par;
    nodes[rx.par].diff = (power[y] - power[x] - up) + (ry.diff - rx.diff);
  }

  int dist(int x,int y){
    Node rx = find(x);
    Node ry = find(y);
    if(rx.par != ry.par) return INF;
    return (ry.diff - rx.diff) + (power[y] - power[x]);
  }

  bool same(int x,int y){
    return find(x).par == find(y).par;
  }
};

int main(){
  int total_players;
  int total_queries;
  while(~scanf("%d %d",
	       &total_players,
	       &total_queries)){
    
    UnionFindTree uft(total_players+1);
    memset(power,0,sizeof(power));
    for(int query_i = 0; query_i <total_queries; query_i++){
      string command;
      cin >> command;
      if(command == "IN"){
	int players[2];
	int up;
	cin >> players[0] >> players[1] >> up;
	power[players[0]] += up;
	power[players[1]] += up;
	uft.unite(players[0],players[1],up);
      }
      else if(command == "COMPARE"){
	int players[2];
	cin >> players[0] >> players[1];
	if(!uft.same(players[0],players[1])){
	  printf("WARNING\n");
	}
	else{
	  printf("%d\n",uft.dist(players[0],players[1]));
	}
      }
    }
  }
}