QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#740750	#9630. 沙堆	huaxiamengjin	TL	5864ms	38204kb	C++23	751b	2024-11-13 11:20:58	2024-11-13 11:21:00

Judging History

你现在查看的是最新测评结果

[2024-11-13 11:21:00]
评测

测评结果：TL
用时：5864ms
内存：38204kb

查看

[2024-11-13 11:20:58]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>g[1001001];
priority_queue<pair<int,int> >q;
int a[1001001];
int main(){
    cin>>n;
    for (int i=1,x,y;i<n;i++)
    cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
    long long sum=0;
    for (int i=1;i<=n;i++)
    cin>>a[i],sum+=(int)g[i].size()-1-a[i];
    if(sum<0)return cout<<-1<<"\n",0;
    for (int i=1;i<=n;i++)
    q.push({a[i],i});
    while(q.size()){
        int x=q.top().second,xx=q.top().first;
        q.pop();if(xx!=a[x]||xx<g[x].size())continue;
        int t=g[x].size();
        for (auto y:g[x])a[y]+=a[x]/t,(a[y]>=g[y].size())&&(q.push({a[y],y}),1);
        a[x]%=t;
    }
    for (int i=1;i<n;i++)
    cout<<a[i]<<" ";cout<<a[n]<<"\n";
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 5684kb

input:

6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1

output:

1 2 0 1 0 0

result:

ok single line: '1 2 0 1 0 0'

Test #2:

score: 0

Accepted

time: 2ms

memory: 5512kb

input:

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

output:

0 1 2 1 1 0 1 1 0 0 0 0

result:

ok single line: '0 1 2 1 1 0 1 1 0 0 0 0'

Test #3:

score: 0

Accepted

time: 2ms

memory: 5680kb

input:

40
1 2
2 3
1 4
3 5
5 6
6 7
4 8
6 9
8 10
6 11
6 12
9 13
10 14
7 15
9 16
15 17
15 18
12 19
18 20
16 21
18 22
22 23
5 24
22 25
2 26
24 27
14 28
27 29
20 30
29 31
30 32
20 33
26 34
26 35
19 36
11 37
34 38
37 39
29 40
3 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 3 0 1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 2 1

output:

1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 1 0 2 1 1 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0

result:

ok single line: '1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 ...0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0'

Test #4:

score: 0

Accepted

time: 5864ms

memory: 38204kb

input:

output:

1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 2 ...

result:

ok single line: '1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #5:

score: -100

Time Limit Exceeded

input: