Problem Links:
poj1988;
Problem:
Cube Stacking
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 11047 | Accepted: 3697 | |
Case Time Limit: 1000MS |
Description
Farmer
John and Betsy are playing a game with N (1 <= N <=
30,000)identical cubes labeled 1 through N. They start with N stacks,
each containing a single cube. Farmer John asks Betsy to perform P
(1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
Input
* Line 1: A single integer, P
* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.
Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.
Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
Output
Print the output from each of the count operations in the same order as the input file.
Sample Input
6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4
Sample Output
1 0 2
Source
USACO 2004 U S Open
Solution:
Disjoint set structure, find-union algorithms.
The solution is in the book of problem Galaxy.
SourceCode
://Mon Jun 7 15:51:10 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX 30001
using namespace std;
class Cube
{
public:
int parent; //The cube at the top of the stack;
int before; //The number of cubes above this cube.
int after; //The number of cubes under this cube, self inclusive;
};
vector<Cube> v(MMAX);
void Makeset(int N)
{
for (int i = 1; i <= N; i++)
{
v[i].parent = i;
v[i].before = 0;
v[i].after = 1;
}
}
int Find(int x)
{
// int depth = 0;
// int p = x;
// while (p != v[p].parent)
// {
// p = v[p].parent;
// depth++;
// }
//
// v[p].after = depth + v[x].after;
// while (x != p)
// {
// int temp = v[x].parent;
// v[x].parent = p;
// v[x].before = depth--;
// v[temp].after = v[x].after + 1;
// x = temp;
// }
// return p;
int p = x;
if (p != v[p].parent)
{
int temp = v[p].parent;
v[p].parent = Find(temp);
v[p].before += v[temp].before;
}
return v[p].parent;
}
void Union(int x, int y)
{
int t1 = Find(x);
int t2 = Find(y);
if (t1 == t2)
return;
v[t2].parent = t1;
// v[y].parent = t1;
// v[x].after += v[t2].after;
// if (x != t1)
// v[t1].after += v[t2].after;
// v[t2].before = v[t1].after;
// if (y != t2)
// v[y].before += v[t1].after;
v[t2].before += v[t1].after;
v[t1].after += v[t2].after;
}
int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N, P;
N = MMAX;
Makeset(N);
cin >> P;
for (int i = 0; i < P; i++)
{
char c;
int x, y;
cin >> c;
if (c == 'M')
{
cin >> x >> y;
Union(x, y);
// cout << v[x].parent << ", " << v[x].before << ", " << v[x].after
// << endl;
// cout << v[y].parent << ", " << v[y].before << ", " << v[y].after
// << endl;
}
else
{
cin >> x;
int t1 = Find(x);
cout << v[t1].after - v[x].before - 1 << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
No comments :
Post a Comment