救救孩子!40pts快调吐了……
查看原帖
救救孩子!40pts快调吐了……
348511
原子げんし楼主2021/3/3 23:06

整整调了一周,实在不知道哪里错了?

//7.21
//rng_58 bless me

#include<bits/stdc++.h>
using namespace std;
//define:
#define REP(i,n) for(int i = 0; i < n; i++)
//#define ll __int128
#define ll long long
//const:
const int MAXN = 100010;
//something:
inline void write(ll x) {
    if(x < 0) {
    	putchar('-');
		x = -x;
	}
    if(x > 9)  {
		write(x / 10);
	}
    putchar(x % 10 + '0');
}
ll ans1[MAXN],ans2[MAXN];
void fun(int id,int x,int y) {
	if(y == 0) {
		return;
	}
	if(ans2[id] == 0) {
		ans1[id] = x; ans2[id] = y;
		return;
	}
	ll xx = ans1[id] * y + ans2[id] * x; ll yy = ans2[id] * y;
	ll gcd = __gcd(xx,yy);
	ans1[id] = xx / gcd; ans2[id] = yy / gcd;
}
int N,M;
vector <int> g[MAXN],ord;
int deg[MAXN];
bool vis[MAXN];
queue <int> q;
//run:
void solve() {
	cin >> N >> M;
	REP(i,N) {
		int K; cin >> K;
		if(!K) {
			ord.push_back(i); continue;
		}
		while(K--) {
			int x; cin >> x; x--;
			g[i].push_back(x); deg[x]++;
		}
	}
	REP(i,N) {
		if(!deg[i]) {
			q.push(i); ans1[i] = 1; ans2[i] = 1;
		}
	}
	while(!q.empty()){
		int x = q.front(); q.pop();
		vis[x] = 1;
		REP(i,g[x].size()) {
			int nx = g[x][i];
			fun(nx,ans1[x],ans2[x] * (1ll * g[x].size())); deg[nx]--;
			if(!deg[nx]) {
				q.push(nx);
			}
		}
	}
	REP(i,ord.size()) {
		write(ans1[ord[i]]); putchar(' '); write(ans2[ord[i]]); puts("");
	}
}
//times:
void Times(int T) {
	while(T--) {
		solve();
	}
}
//begin:
int main() {
	int T = 1;
	//cin >> T;
	Times(T);
	return 0;
}
2021/3/3 23:06
加载中...