QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740299#9630. 沙堆huaxiamengjinTL 16ms36632kbC++141.7kb2024-11-13 08:41:392024-11-13 08:41:40

Judging History

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

  • [2024-11-13 08:41:40]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:36632kb
  • [2024-11-13 08:41:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>g[1001001];
int a[1001001];
set<int>s;
int fa[1001001];
int tot,dfn[1001001],sz[1001001],idfn[1001001];
void dfs(int x,int pa){
    dfn[x]=++tot,sz[x]=1;
    idfn[tot]=x;fa[x]=pa;
    for (auto y:g[x])if(y!=pa){
        dfs(y,x);sz[x]+=sz[y];
    }
}
void del(int x){
    if(a[x]<(int)g[x].size()-1)
    s.erase(dfn[x]);
}
void ins(int x){
    if(a[x]<(int)g[x].size()-1)
    s.insert(dfn[x]);
}
void dfs2(int x,int pa){
    for (auto y:g[x])if(y!=pa)dfs2(y,x);
    while(a[x]>=g[x].size()){
        a[x]--;a[fa[x]]++;
        int now=dfn[x]+1;
        // cout<<a[x]<<" "<<g[x].size()<<"@@@@@@\n";
        while(now<dfn[x]+sz[x]){
            
            auto it=s.lower_bound(now);
            // cout<<x<<"!!!!!!"<<now<<"\n";
            if(it==s.end())break;
            if((*it)>=dfn[x]+sz[x])break;
            int itt=idfn[*it];
            // cout<<now<<" "<<itt<<" "<<fa[itt]<<"@@!!!\n";
            del(itt);del(fa[itt]);
            a[itt]++,a[fa[itt]]--;
            ins(itt);ins(fa[itt]);
            now=dfn[itt]+sz[itt];
        }
    }
  
    // cout<<x<<"@@@@@@\n";
    // for (int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<"\n";
    // for (int i=1;i<=n;i++)cout<<g[i].size()<<" ";cout<<"\n";
    // for (auto i:s)cout<<idfn[i]<<" ";cout<<"\n";  
    ins(x);
}
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;
    dfs(1,1);dfs2(1,1);
    for (int i=1;i<n;i++)
        cout<<a[i]<<" ";
    cout<<a[n]<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 35076kb

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: 9ms
memory: 33356kb

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: 9ms
memory: 33964kb

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: 16ms
memory: 34840kb

input:

5000
1 2
1 3
2 4
4 5
3 6
5 7
7 8
6 9
8 10
9 11
10 12
11 13
13 14
14 15
12 16
16 17
15 18
17 19
16 20
18 21
16 22
15 23
20 24
24 25
25 26
22 27
23 28
19 29
27 30
29 31
27 32
28 33
32 34
31 35
26 36
34 37
35 38
35 39
33 40
38 41
40 42
42 43
30 44
41 45
37 46
39 47
47 48
36 49
48 50
46 51
44 52
51 53
4...

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: 0
Accepted
time: 15ms
memory: 36632kb

input:

5000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
7 10
9 11
10 12
6 13
11 14
12 15
13 16
16 17
14 18
17 19
17 20
19 21
15 22
21 23
22 24
18 25
23 26
24 27
25 28
28 29
27 30
29 31
26 32
30 33
19 34
34 35
32 36
20 37
37 38
31 39
35 40
39 41
40 42
42 43
41 44
33 45
43 46
38 47
46 48
45 49
48 50
44 51
49 52
51 53
50...

output:

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 1 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 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 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 1 1 1 1 1 1 1 0 1 1 ...

result:

ok single line: '1 1 1 1 1 2 1 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 #6:

score: 0
Accepted
time: 14ms
memory: 33836kb

input:

5000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
7 10
10 11
9 12
11 13
12 14
13 15
15 16
14 17
17 18
16 19
18 20
19 21
21 22
20 23
22 24
23 25
24 26
26 27
25 28
28 29
27 30
29 31
31 32
30 33
32 34
33 35
35 36
34 37
36 38
37 39
39 40
38 41
40 42
31 43
41 44
43 45
44 46
42 47
46 48
45 49
48 50
49 51
51 52
52 53
5...

output:

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 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 1 1 1 2 0 1 2 1 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 1 1 3 1 2 1 1 1 1 2 1 2 1 2 1 1 2 1 1 1 1 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 1 1 1 1 2 1 1 ...

result:

ok single line: '1 1 1 1 1 1 1 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 #7:

score: 0
Accepted
time: 16ms
memory: 35284kb

input:

5000
1 2
1 3
2 4
3 5
5 6
4 7
7 8
6 9
9 10
10 11
8 12
11 13
13 14
12 15
14 16
16 17
7 18
15 19
18 20
19 21
17 22
22 23
20 24
24 25
23 26
21 27
25 28
27 29
29 30
28 31
26 32
31 33
30 34
32 35
35 36
34 37
33 38
38 39
39 40
40 41
37 42
41 43
43 44
42 45
36 46
44 47
45 48
46 49
48 50
47 51
43 52
49 53
52...

output:

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 0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 2 1 1 1 2 0 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 0 1 1 0 2 1 1 1 0 2 1 1 1 0 1 1 1 0 0 1 1 1 1 1 2 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 4 0 1 0 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok single line: '1 1 1 1 1 1 2 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 #8:

score: 0
Accepted
time: 13ms
memory: 34388kb

input:

5000
1 2
1 3
2 4
3 5
5 6
4 7
6 8
8 9
8 10
10 11
9 12
11 13
7 14
13 15
12 16
14 17
15 18
16 19
18 20
19 21
20 22
17 23
21 24
24 25
23 26
26 27
22 28
25 29
27 30
28 31
31 32
30 33
32 34
33 35
34 36
35 37
37 38
38 39
36 40
40 41
39 42
29 43
42 44
44 45
42 46
46 47
41 48
47 49
49 50
45 51
43 52
51 53
48...

output:

1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 1 1 0 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 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 1 2 1 1 1 1 1 1 1 1 1 3 1 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 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 ...

result:

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

Test #9:

score: 0
Accepted
time: 16ms
memory: 34064kb

input:

5000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
7 10
8 11
9 12
10 13
11 14
13 15
14 16
15 17
17 18
16 19
17 20
12 21
18 22
20 23
21 24
24 25
23 26
20 27
22 28
28 29
25 30
29 31
27 32
30 33
32 34
34 35
33 36
30 37
36 38
31 39
35 40
37 41
26 42
39 43
38 44
19 45
42 46
44 47
40 48
46 49
49 50
45 51
48 52
47 53
50...

output:

1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 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 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 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 2 1 1 1 1 1 1 1 1 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 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 ...

result:

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

Test #10:

score: 0
Accepted
time: 16ms
memory: 35420kb

input:

5000
1 2
2 3
1 4
3 5
4 6
5 7
6 8
7 9
6 10
6 11
10 12
11 13
13 14
12 15
9 16
14 17
15 18
16 19
17 20
18 21
21 22
22 23
18 24
20 25
23 26
25 27
8 28
28 29
26 30
24 31
27 32
19 33
30 34
29 35
33 36
34 37
37 38
35 39
34 40
32 41
36 42
42 43
39 44
43 45
44 46
45 47
46 48
41 49
47 50
49 51
48 52
52 53
50 ...

output:

1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 0 1 1 1 3 1 1 1 1 1 1 1 1 2 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 2 1 1 1 1 1 1 1 1 1 1 4 1 1 1 2 ...

result:

ok single line: '1 1 1 1 1 3 1 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 #11:

score: 0
Accepted
time: 12ms
memory: 35276kb

input:

5000
1 2
2 3
3 4
4 5
1 6
6 7
7 8
5 9
8 10
10 11
9 12
12 13
11 14
13 15
10 16
15 17
14 18
17 19
17 20
16 21
20 22
19 23
22 24
23 25
24 26
25 27
25 28
21 29
18 30
26 31
27 32
30 33
31 34
32 35
34 36
36 37
37 38
38 39
35 40
39 41
40 42
29 43
41 44
44 45
42 46
41 47
43 48
28 49
47 50
46 51
50 52
51 53
5...

output:

1 1 1 1 1 1 1 1 1 2 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 1 1 1 1 2 2 1 1 1 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 1 1 1 1 1 2 0 1 2 1 2 1 0 1 1 1 1 1 1 1 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 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 ...

result:

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

Test #12:

score: 0
Accepted
time: 12ms
memory: 34168kb

input:

5000
1 2
1 3
3 4
2 5
4 6
6 7
5 8
7 9
8 10
9 11
10 12
3 13
11 14
14 15
11 16
13 17
17 18
16 19
15 20
20 21
21 22
18 23
19 24
22 25
12 26
24 27
27 28
25 29
26 30
29 31
30 32
23 33
30 34
34 35
33 36
35 37
32 38
37 39
36 40
18 41
39 42
28 43
41 44
31 45
43 46
44 47
40 48
46 49
47 50
49 51
42 52
38 53
45...

output:

1 1 2 1 1 1 1 1 1 1 2 1 1 1 0 1 1 2 1 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 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 0 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 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 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

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

Test #13:

score: -100
Time Limit Exceeded

input:

1000000
1 2
1 3
2 4
3 5
4 6
5 7
7 8
8 9
9 10
8 11
6 12
12 13
13 14
11 15
15 16
14 17
16 18
11 19
15 20
18 21
10 22
22 23
19 24
20 25
15 26
25 27
25 28
28 29
17 30
30 31
29 32
30 33
24 34
31 35
34 36
33 37
23 38
28 39
32 40
26 41
21 42
42 43
27 44
39 45
36 46
43 47
37 48
34 49
44 50
47 51
50 52
48 53...

output:


result: