社区讨论
求问
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 条回复,欢迎继续交流。
正在加载回复...