社区讨论

求问

P7113[NOIP2020] 排水系统参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhizew3r
此快照首次捕获于
2025/11/03 18:13
4 个月前
此快照最后确认于
2025/11/03 18:13
4 个月前
查看原帖
RT,去年在CQ集训时考场AC的题,似乎没用拓扑排序但为什么AC了
CPP
#include<cstdio>
#include<vector>
#include<algorithm>
#define int __int128
#define PII pair<int,int>
#define fir first
#define sec second
using namespace std;
const int N=1e5+7;
int n,m,d;
int q[N],a[N],f[N];
vector<int> s[N];
vector<PII> c[N];
vector<int> ans;
inline int read(){
		int x=0,f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-'){
				f=-1;
			}
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			x=(x<<1)+(x<<3)+(c^48);
			c=getchar();
		}
		return x*f;
	}
	inline void write(int x){
		if(x<0){
			x=-x;
			putchar('-');
		}
		if(x>9){
			write(x/10),putchar(x%10+'0');
		}
		else{
			putchar(x+'0');
		}
		return ;
	}
inline int gcd(int a,int b){
	return !b?a:gcd(b,a%b);
}
inline void dis(int x){
	int fm=1,fz=0;
	for(auto i:c[x]){
		fm*=i.sec;
	}
	for(auto i:c[x]){
		fz+=(fm/i.sec)*i.fir;
	}
	int l=gcd(fm,fz);
	fm=fm/l,fz=fz/l;
	c[x].clear();
	c[x].push_back({fz,fm});
	return ;
}
inline void dfs(int root){
	if(!f[root]){
		return ;
	}
	dis(root);
	int x=c[root][0].fir,y=c[root][0].sec;
	for(auto i:s[root]){
		c[i].push_back({x,y*f[root]});
		dis(i);
	}
	c[root].clear();
	for(auto i:s[root]){
		dfs(i);
	}
	return ;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		d=read();
		if(!d){
			ans.push_back(i);
		}
		f[i]=d;
		for(int k=0,r;k<d;k++){
			r=read();
			s[i].push_back(r);
		}
	}
	for(int i=1;i<=m;i++){
		c[i].push_back({1,1});
	}
	for(int i=1;i<=m;i++){
		dfs(i);
	}
	for(auto i:ans){
		dis(i);
		write(c[i][0].fir);
		putchar(' ');
		write(c[i][0].sec);
		putchar('\n');
	}
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...