| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
1A#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include <vector>
using namespace std;
int number = 0;
map<string, int> si;
long long int val[64], rel[64];
int rep[64];
long long int GCD(long long int a, long long int b){
if(a==0) return b;
if(b==0) return a;
if(a>b) return GCD(b, a%b);
return GCD(a, b%a);
}
int getNumber(string s){
map<string, int>::iterator it = si.find(s);
if(it != si.end()) return it->second;
si.insert(pair<string, int>(s, number));
rep[number] = number;
val[number] = rel[number] = 1;
number++;
return number-1;
}
int getRep(int x){
//find the representative of x
int start = x;
vector<int> path;
while(rep[start] != start){
path.push_back(start);
start = rep[start];
}
int sz = path.size();
for(int i = sz-2; i >= 0; i--){
rep[path[i]] = start;
long long int Val = val[path[i]] * val[path[i+1]], Rel = rel[path[i]] * rel[path[i+1]];
long long int gcd = GCD(Val, Rel);
Val /= gcd;
Rel /= gcd;
val[path[i]] = Val, rel[path[i]] = Rel;
}
return start;
}
void setUnion(int x, int y, long long int numX, long long int numY){
int repX = getRep(x), repY = getRep(y);
rep[repY] = repX;
long long int Val = val[x] * numX * rel[y], Rel = rel[x] * numY * val[y];
long long int gcd = GCD(Val, Rel);
Val /= gcd;
Rel /= gcd;
val[repY] = Val, rel[repY] = Rel;
}
int main() {
char cmd, denghao;
while(cin >> cmd){
if(cmd == '.') break;
else if(cmd == '!'){
string sX, sY;
long long int numX, numY;
cin >> numX >> sX >> denghao >> numY >> sY;
int x = getNumber(sX), y = getNumber(sY);
setUnion(x, y, numX, numY);
}
else if(cmd == '?'){
string sX, sY;
cin >> sX >> denghao >> sY;
int x = getNumber(sX), y = getNumber(sY);
int repX = getRep(x), repY = getRep(y);
if(repX != repY){
cout << "? " << sX << " = ? " << sY << endl;
}
else{
long long int Val = val[x] * rel[y], Rel = rel[x] * val[y];
long long int gcd = GCD(Val, Rel);
Val /= gcd, Rel /= gcd;
cout << Rel << " " << sX << " = " << Val << " " << sY << endl;
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator