Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A

Posted by KatrineYang at 2016-11-25 14:01:37 on Problem 1570
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator