Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#478#93. 「NOIP2020」排水系统Dtw60379ms11548kbC++231.5kb2025-04-25 09:24:422025-04-25 09:24:43

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define ll long long
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,in[100001],out[100001],book[100001];
ll xx[100001],yy[100001];
ll gcd(ll x,ll y){
	if(y==0)
		return x;
	return gcd(y,x%y);
}
void add(int u,ll x,ll y){
	if(y==0)
		return;
	if(yy[u]==0){
		xx[u]=x;
		yy[u]=y;
		return;
	}
	ll p1=xx[u]*y+yy[u]*x;
	ll p2=yy[u]*y;
	ll p3=gcd(p1,p2);
	xx[u]=p1/p3;
	yy[u]=p2/p3;
	return;
}
vector<int> a[500001];
queue<int> q;
void tp(){
	for(int i=1;i<=n;i++)
		if(!in[i]){
			book[i]=1;
			q.push(i);
			xx[i]=1,yy[i]=1;
		}
	while(!q.empty()){
		int p=q.front();
		q.pop();
		if(out[p])
			continue;
		for(int i=0;i<a[p].size();i++){
			add(a[p][i],xx[p],yy[p]*(1ll*a[p].size()));
			if(book[a[p][i]])
				continue;
			in[a[p][i]]--;
			if(in[a[p][i]]==0){
				book[a[p][i]]=1;
				q.push(a[p][i]);
			}
		}
	}
	return;
}
int main()
{
	//freopen("water.in","r",stdin);
	//freopen("water.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		int d=read();
		if(d==0){
			out[i]=1;
			continue;
		}
		while(d--){
			int v;
			v=read();
			a[i].push_back(v);
			in[v]++;
		}
	}
	tp();
	for(int i=1;i<=n;i++){
		if(out[i]){
			add(i,0,1);
			printf("%lld %lld\n",xx[i],yy[i]);
		}
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 3ms
memory: 7608kb

input:

10 1
4 2 3 4 5
3 6 7 8
3 7 10 8
1 7
2 8 10
2 8 9
2 9 8
1 10
1 10
0

output:

1 1

result:

ok 2 tokens

Test #2:

score: 10
Accepted
time: 3ms
memory: 5612kb

input:

10 1
5 2 3 4 5 7
3 6 7 9
3 7 8 9
3 8 9 6
1 7
2 9 10
2 10 9
0
0
0

output:

2 15
8 15
1 3

result:

ok 6 tokens

Test #3:

score: 10
Accepted
time: 3ms
memory: 7600kb

input:

10 1
5 2 3 4 5 8
4 6 8 7 9
2 7 6
4 8 6 9 10
2 9 8
1 10
0
0
1 10
0

output:

3 20
2 5
9 20

result:

ok 6 tokens

Test #4:

score: 10
Accepted
time: 5ms
memory: 7580kb

input:

1000 1
5 2 3 4 5 468
5 6 7 8 9 72
5 10 11 12 13 658
5 14 15 16 17 100
5 18 19 20 21 129
5 22 23 24 2...

output:

1 625
1 625
1 625
1 625
1 625
1 625
1 625
1 3125
1 3125
2 3125
3 3125
2 3125
47 37500
1 2500
1 2500
...

result:

ok 636 tokens

Test #5:

score: 10
Accepted
time: 5ms
memory: 5720kb

input:

1000 1
5 2 3 4 5 257
5 6 7 8 9 948
5 10 11 12 13 633
5 14 15 16 17 1000
5 18 19 20 21 105
5 22 23 24...

output:

1 625
1 625
6 625
2 625
1 625
1 625
1 625
1 625
1 625
1 625
1 500
1 1875
1 1250
1 2500
9 6250
1 2500...

result:

ok 626 tokens

Test #6:

score: 10
Accepted
time: 2ms
memory: 5460kb

input:

1000 1
5 2 3 4 5 799
5 6 7 8 9 587
5 10 11 12 13 694
5 14 15 16 17 865
5 18 19 20 21 10
5 22 23 24 2...

output:

1 625
1 625
1 625
1 625
1 625
1 625
2 625
6 625
9 6250
9 2500
1 2000
9 10000
1 2500
1 2500
1 2500
2 ...

result:

ok 652 tokens

Test #7:

score: 0
Wrong Answer
time: 73ms
memory: 11360kb

input:

100000 1
5 2 3 4 5 7783
5 6 7 8 9 21991
5 10 11 12 13 45651
5 14 15 16 17 56745
5 18 19 20 21 84002
...

output:

1 15625
1 15625
1 15625
1 15625
1 15625
1 78125
1 62500
1 78125
1 78125
1 78125
1 78125
1 78125
2 78...

result:

wrong answer 74611th words differ - expected: '556349', found: '16299287109375'

Test #8:

score: 0
Wrong Answer
time: 72ms
memory: 10960kb

input:

100000 1
5 2 3 4 5 6025
5 6 7 8 9 32221
5 10 11 12 13 39240
5 14 15 16 17 55392
5 18 19 20 21 69386
...

output:

1 12500
1 15625
1 15625
1 15625
1 15625
1 12500
1 15625
1 12500
1 12500
1 15625
1 15625
1 15625
1 12...

result:

wrong answer 10851st words differ - expected: '264901', found: '23282314453125'

Test #9:

score: 0
Wrong Answer
time: 107ms
memory: 11548kb

input:

100000 10
5 11 12 13 14 15
3 66 67 68
4 96 97 98 99
5 1274 1643 2223 2242 2626
5 5407 8119 10748 198...

output:

1 48828125
2538341 10546875000
15673 2343750000
759673 2343750000
54145169317349 3023308800000000000...

result:

wrong answer 19th words differ - expected: '7805087', found: '76221552734375'

Test #10:

score: 0
Wrong Answer
time: 106ms
memory: 10080kb

input:

100000 10
5 11 12 13 14 15
3 66 67 68
4 98 99 100 101
5 193 213 239 613 1656
5 187 259 453 513 3129
...

output:

1 48828125
1 48828125
-1120408001953125 656607893427387904
22139845916015625 -5986637891203072
21419...

result:

wrong answer 5th words differ - expected: '191216299', found: '-1120408001953125'