int128求助,WA后四个点,悬关
查看原帖
int128求助,WA后四个点,悬关
1000268
PassionOfLife楼主2023/11/9 12:58

用了__int128,但还是不能过后四个点:

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll __int128
using namespace std;

const int N = 1e5 + 10;
const int M = 5*N;

int gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a%b);}

int lcm(ll GCD, ll a, ll b) {return a /GCD * b;}

struct Frac {
	ll a;
	ll b;
	
	void yuefen() {
		ll GCD = gcd(a, b);
		a /= GCD;
		b /= GCD;
	}
	
	void tongfen(ll x) {
		ll times = x / b;
		b = x;
		a *= times;
	}
	
	Frac operator / (ll x) {
		Frac temp = *this;
		temp.b *= x;
		temp.yuefen();
		return temp;
	}
	
	Frac operator + (const Frac& x) {
		Frac t1 = *this;
		Frac t2 = x;
		
		ll LCM = lcm(gcd(t1.b, t2.b), t1.b, t2.b);
		t1.tongfen(LCM); t2.tongfen(LCM);
		
		t1.a = t1.a + t2.a;
		t1.yuefen();
		
		return t1;
	}
	
	Frac operator = (const Frac& x) {
		this->a = x.a;
		this->b = x.b;
	}
};

ll read() {
	ll s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')	{if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {s = s*10 + ch - '0'; ch = getchar();}
	return s*w;
}

void write(ll n) {
	if(n >= 10)	write(n/10);
	putchar(n%10 + '0');
}

int h[N], e[M], ne[M], idx; //链式前向星
int indeg[N]; //入度
int n, m;
vector<int> last; //最终结点
Frac water[N];
int d[N]; //出度

void init_G() {
	memset(h, -1, sizeof(h));
	memset(ne, -1, sizeof(ne));
	idx = 0;
	memset(indeg, 0, sizeof(indeg));
}

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void init_() {
	init_G();
	scanf("%d%d", &n, &m);
	for(int i = 1; i<=n; i++) {
		scanf("%d", &d[i]);
		if(d[i] == 0)	last.push_back(i); 
		for(int j = 0; j<d[i]; j++) {
			int k; scanf("%d", &k);
			add(i, k);
			indeg[k]++;
		}
	}
	
	for(int i = 1; i<=n; i++)
		water[i] = {0, 0}; 
}

void solve() {
	queue<int> q;
    //找初始点
	for(int i = 1; i<=n; i++) {
		if(indeg[i] == 0 && !vis[i]) {
			q.push(i);
			water[i] = {1, 1};
		}
	}
	
	while(!q.empty()) {
		int t = q.front(); q.pop();
		for(int p = h[t]; p != -1; p = ne[p]) {
			int node = e[p];
			if(water[node].a == 0 && water[node].b == 0) //分母为0特判
				water[node] = water[t] / d[t];
			else
				water[node] = water[node] + (water[t] / d[t]);
			if(--indeg[node] == 0)	q.push(node);
		}
	}
	
	for(int i : last)	water[i].yuefen(); 
	
	sort(last.begin(), last.end());
	for(int i : last) {
		write(water[i].a); putchar(' '); write(water[i].b); putchar('\n');
	}
}

int main() {
	init_();
	solve();
	return 0;
}
2023/11/9 12:58
加载中...