#2325265

Solution for 0520: Lightest Mobile by olphe

Source Code Status Test Cases
    Policy: public     Reviewed: 19    
00.00 sec    3184 KB    126 lines     2533 bytes    2017-05-19 04:01
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N;
list<int>P;
list<long long int>ans;

int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	P.push_back(2);
	for (int i = 3; i < pow(2,16); i += 2) {
		bool flag = true;
		for (auto j : P) {
			if (i%j == 0) {
				flag = false;
				break;
			}
			if (j*j > i)break;
		}
		if (flag)P.push_back(i);
	}
	while (N) {
		vector<long long int>l(N);
		vector<long long int>r(N);
		vector<int>lx(N);
		vector<int>rx(N);
		vector<long long int>lw(N);
		vector<long long int>rw(N);
		vector<bool>flag(N, true);
		stack<int>node;
		for (int i = 0; i < N; i++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			c--;
			d--;
			for (auto i : P) {
				while (a%i == 0 && b%i == 0) {
					a /= i;
					b /= i;
				}
				if (min(a, b) < i)break;
			}
			l[i] = a;
			r[i] = b;
			lx[i] = c;
			rx[i] = d;
			if (c == -1 && d == -1) {

				lw[i] = r[i];
				rw[i] = l[i];
			}
			else if (c == -1)lw[i] = 1;
			else if (d == -1)rw[i] = 1;
			if (c >= 0)flag[c] = false;
			if (d >= 0)flag[d] = false;
		}
	//	cout << "hijiki";
		for (int i = 0; i < N; i++) {
			if (flag[i]) {
				node.push(i);
			}
		}
		while (!node.empty()) {
			int current = node.top();
			bool con = false;
			if (lx[current] >= 0) {
				if (lw[lx[current]] && rw[lx[current]])lw[current] = lw[lx[current]] + rw[lx[current]];
				else {
					node.push(lx[current]);
					con = true;
				}
			}
			if (rx[current] >= 0) {
				if (lw[rx[current]] && rw[rx[current]])rw[current] = lw[rx[current]] + rw[rx[current]];
				else {
					node.push(rx[current]);
					continue;
				}
			}
			if (con)continue;
			if (l[current] * lw[current] != r[current] * rw[current]) {
				long long int a = r[current] * rw[current];
				long long int b = l[current] * lw[current];
				for (auto i : P) {
					while(a%i==0&&b%i==0){
						a /= i;
						b /= i;
					}
					if (min(a, b) < i)break;
				}
				lw[current] *= a;
				rw[current] *= b;
			}
		//	cout << current << " " << lw[current] << " " << rw[current] << endl;
			node.pop();
		}
		for (int i = 0; i < N; i++) {
			if (flag[i]) {
				ans.push_back(lw[i] + rw[i]);
				//cout << lw[i] + rw[i] << endl;
				break;
			}
		}
		cin >> N;
	}
	for (auto i : ans)cout << i << endl;
	return 0;
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++14 CPU: 00.00 sec Memory: 3184 KB Length: 2533 B 2017-05-19 04:01 2017-05-19 04:01
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3184 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags