代码求调
查看原帖
代码求调
740001
a_can_of_preserves楼主2024/7/19 17:25

P7113 [NOIP2020] 排水系统 求调

写重载写炸了,求调!!

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int MAXN=  1e5 + 5;

int n, m;
int ind[MAXN], oud[MAXN];

int q[MAXN], head = 1, tail;

__int128 d[MAXN];

vector<int> vec[MAXN];

__int128 gcd(__int128 x, __int128 y){
	return y == 0 ? x : gcd(y, x % y);
}

__int128 lcm(__int128 x, __int128 y){
	return x / gcd(x, y) * y;
}

struct Drainage_Node_Data{
	__int128 numerator, denominator;
}dp[MAXN], tmp_data, tmp_data_2, xx, yy, zz;

Drainage_Node_Data operator+ (const Drainage_Node_Data x, const Drainage_Node_Data y){
	__int128 tmp_lcm = gcd(x.denominator, y.denominator);
	__int128 multiple_of_x = tmp_lcm / x.denominator;
	__int128 multiple_of_y = tmp_lcm / y.denominator;
	__int128 tmp_numerator = x.numerator * multiple_of_x + y.numerator * multiple_of_y;
	return {tmp_numerator, tmp_lcm};
}

Drainage_Node_Data operator/ (const Drainage_Node_Data x, const __int128 d){
	__int128 tmp_denominator = x.denominator * d;
	__int128 tmp_gcd = gcd(x.numerator, tmp_denominator);
	__int128 tmp_numerator = x.numerator / tmp_gcd;
	tmp_denominator = tmp_denominator / tmp_gcd;
	return {tmp_numerator, tmp_denominator};
}

void print_of_int128(const __int128 x){
	print_of_int128(x / 10);
	putchar(x % 10 + '0');
}

void top_sort(){
	for(int i = 1; i <= n; i++){
		if(ind[i] == 0){
			continue;
		}
		q[++tail] = i;
	}
	while(head <= tail){
		int u = q[head++];
		for(int v : vec[u]){
			tmp_data = (dp[u] / d[u]);
			tmp_data_2 = (tmp_data / 1);
			dp[v] = tmp_data;
			dp[v] = (dp[v] + tmp_data);
			if(--ind[v] == 0){
				q[++tail] = v;
			}
		}
	}
}

void output(){
	for(int i = 1; i <= n; i++){
		if(oud[i] == 0){
			print_of_int128(dp[i].numerator);
			cout << ' ';
			print_of_int128(dp[i].numerator);
			cout << '\n';
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		int d;
		cin >> d;
		for(int j = 1; j <= d; j++){
			int v;
			cin >> v;
			vec[i].push_back(v);
			ind[v]++;
			oud[i]++;
		}
	}
	xx + yy;
	top_sort();
	output();

	return 0;
}

2024/7/19 17:25
加载中...