ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#478 | #93. 「NOIP2020」排水系统 | Dtw | 60 | 379ms | 11548kb | C++23 | 1.5kb | 2025-04-25 09:24:42 | 2025-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'