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