China NOI 2002: Legend of Galactic Heroes

NOI China 2002: Legend of Galactic Heroes

Original Problem Statement

描述

公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。
宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。
杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。
然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。
在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。
作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。
最终的决战已经展开，银河的历史又翻过了一页……
格式

输入格式

输入的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。
以下有T行，每行有一条指令。指令有两种格式：
1.M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
2.C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。
输出格式

你的程序应当依次对输入的每一条指令进行分析和处理：
如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
样例1

样例输入1

4
M 2 3
C 1 2
M 2 4
C 4 2
Copy
样例输出1

-1
1
Copy
限制

2秒

My translation (Redundant information removed)

There are 30K columns in a grid. There are also 30K numbered dots to be put and rearranged in the grid. Initially, only the nth dot is in the nth row. However, merge commands in the format "M i j" merges the contents of the column containing dot i and the column containing dot j together. After several merge commands, the grid is reformed. Another type of command, "C i j", queries whether or not dot i and dot j are in the same column. If so, then it returns the number of dots between i and j, if not, it returns -1. Write a program that parses and runs these commands.

The Algorithm and Specifications

This problem uses an extended disjoint-set data structure. The normal DSDS is extended with two extra parameters, "before" and "count". These parameters store how many nodes are behind it in its tree (its height, or its location in a column) and how many nodes are in front of it. These parameters, being updated every find() and unify() call, accurately describe its location in its column. This is the core part of the problem apart for DSDS. My program describes the method in further depth through comments:

The Code Itself

#include <cstdio>
#include <cstdlib>
using namespace std;

int father[30001],before[30001],count[30001]; // Define arrays: store ancestors, amount of nodes behind them or in front:
                                              // <--before[node]------><{Node}------count[node]---->

void makeset()                                // Initialize set:
{
for (int i=1; i<=30000; i++)              // for each index initialize it for:
    {
   father[i]=i;                           // everyone is their own ancestor,
   before[i]=0;                           // they are not connected,
   count[i]=1;                            // and they are by themselves.
    }
}
int find(int v)                               // Locate furthest ancestor process:
{
    if(father[v]==v) return v;                // If it is the top of the tree (aka it is its own ancestor), then stop.
    int b = father[v];                        // Else, record v's current ancestor,
    father[v]=find(father[v]);                // update v's ancestor by going further up the tree,
    before[v]=before[v]+before[b];            // and update the amount of nodes behind them.
    return father[v];                         // The answer is the updated ancestor variable
}
void unify(int x, int y)                      // Merge x and y tree process:
{
int fx,fy; fx=find(x); fy=find(y);        // Locate the tree roots.
    if (fx==fy) return;                       // Who merges the same trees?
father[fx]=fy;                            // Connect them,
    before[fx]+=count[fy];                    // and update their location in the tree,
    count[fy]+=count[fx];                     // and their depth in the tree.
}
int main()                                    // The main process:
{
    int n; scanf("%d\n",&n);                  // Read the command amount,
    makeset();                                // plant the forest,
    for(int i=0;i<n;i++)                      // and read the commands:
    {
        char c; int p1, p2;                   // The character c is the command type and p1 and p2 are parameters
scanf("%c %d %d\n",&c,&p1,&p2);       // We read them, noting the newline,
        if(c=='M') unify(p1,p2);              // and parse command types: c="M" means unify p1 and p2
        else if(c=='C')                       // while c="C" requests the fruit distance between p1 and p2.
        {
            if(find(p1)==find(p2)) printf("%d\n", abs(before[p1]-before[p2])-1);
            else printf("-1\n");              // If undefined, the answer is -1
        }
    }
    
}