ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#457 | #91. 「NOIP2020」移球游戏 | ryp | 0 | 0ms | 0kb | C++14 | 1.5kb | 2025-04-24 13:56:04 | 2025-04-24 13:56:05 |
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: 0
Checker Judgement Failed
input:
2 20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1
output:
result:
Test #2:
score: 0
Checker Judgement Failed
input:
2 20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1
output:
result:
Test #3:
score: 0
Checker Judgement Failed
input:
10 20 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 4 7 2 9 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 10 3 4 1...
output:
result:
Test #4:
score: 0
Checker Judgement Failed
input:
10 20 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 2 3 2 9 3 3 3 3 3 3 3 ...
output:
result:
Test #5:
score: 0
Checker Judgement Failed
input:
10 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 6 1 6 8 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 2 1 10 3 2 2 2 2 2 2 2...
output:
result:
Test #6:
score: 0
Checker Judgement Failed
input:
50 85 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 32 21 34 48 29 15 10 26 23 10 30 39 29 11 37 10 2...
output:
result:
Test #7:
score: 0
Checker Judgement Failed
input:
50 85 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1...
output:
result:
Test #8:
score: 0
Checker Judgement Failed
input:
50 85 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 28 46 38 39 49 21 39 7 17 18 34 2 34 39 3 44 42 2...
output:
result:
Test #9:
score: 0
Checker Judgement Failed
input:
50 300 28 28 28 28 28 28 28 28 28 28 28 28 28 28 28 2 35 41 4 35 30 2 10 16 36 2 34 10 36 32 18 11 2...
output:
result:
Test #10:
score: 0
Checker Judgement Failed
input:
50 300 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 26 48 48 49 45 48 4 10 27 19 50 30 24 16 9 41 14 19 19 41 15 7 ...
output:
result:
Test #11:
score: 0
Checker Judgement Failed
input:
50 300 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 37 15 25 13 21 35 45 26 26 48 20 38 13 35 15 33 8 16 16 33 1 27...
output:
result:
Test #12:
score: 0
Checker Judgement Failed
input:
50 300 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 44 16 43 44 28 25 21 33 12 1 26 22 25 16 4 47 20...
output:
result:
Test #13:
score: 0
Checker Judgement Failed
input:
50 300 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 39 15 50 10 9 11 33 24 7 29 31 32 24 50 19 25 18 4 19 40 38 9 6...
output:
result:
Test #14:
score: 0
Checker Judgement Failed
input:
50 300 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 26 26 32 15 40 24 49 16 2 35 20 19 23 12 50 44 2...
output:
result:
Test #15:
score: 0
Checker Judgement Failed
input:
50 400 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 ...
output:
result:
Test #16:
score: 0
Checker Judgement Failed
input:
50 400 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 42 1 23 50 36 5 41 5 36 17 14 41 47 19 8 20 21 2...
output:
result:
Test #17:
score: 0
Checker Judgement Failed
input:
50 400 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 25 27 49 4 5 27 9 42 20 43 37 12 22 1 17 34 8 29 6 39 30 30 49 ...
output:
result:
Test #18:
score: 0
Checker Judgement Failed
input:
50 400 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 47 5 39 47 4 16 43 19 34 45 25 26 50 1 25 41 46 ...
output:
result:
Test #19:
score: 0
Checker Judgement Failed
input:
50 400 50 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 ...
output:
result:
Test #20:
score: 0
Checker Judgement Failed
input:
50 400 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 ...