QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#570172#8296. Constructing Ranchesship2077TL 1191ms10228kbC++232.2kb2024-09-17 14:28:402024-09-17 14:28:40

Judging History

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

  • [2024-09-17 14:28:40]
  • 评测
  • 测评结果：TL
  • 用时：1191ms
  • 内存：10228kb
查看
  • [2024-09-17 14:28:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=2e5+5;
vector<int>adj[M],tmp,vec;
int rt,sum,Min,rec,a[M],tr[M],siz[M],rec1[M];
long long ans,rec2[M],lsh[M];bool vis[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
void findroot(int x,int f){
    siz[x]=1; int mx=0;
    for (auto y:adj[x]){
        if (y==f||vis[y]) continue;
        findroot(y,x);mx=max(mx,siz[y]);
        siz[x]+=siz[y];
    } mx=max(mx,sum-siz[x]);
    if (mx<Min) Min=x,rt=x;
}
void getans(vector<int>tmp,int coef){
    sort(tmp.begin(),tmp.end(),[&](int x,int y){return rec1[x]<rec1[y];});
    int num=0;for (auto x:tmp) lsh[++num]=rec2[x];
    sort(lsh+1,lsh+num+1);num=unique(lsh+1,lsh+num+1)-lsh-1;
    for (int i=1;i<=num;i++) tr[i]=0;
    auto update=[&](auto x){while (x<=num) tr[x]++,x+=x&-x;};
    auto query=[&](auto x){int res=0;while (x) res+=tr[x],x-=x&-x;return res;};
    for (int i=0;i<tmp.size();i++){
        const int x=tmp[i];
        ans+=(i-query(upper_bound(lsh+1,lsh+num+1,rec1[x]*2-rec2[x]+rec)-lsh-1))*coef;
        update(lower_bound(lsh+1,lsh+num+1,rec2[x])-lsh);
    }
}
void dfs(int x,int f){
    siz[x]=1;
    rec1[x]=max(a[x],rec1[f]);
    rec2[x]=a[x]+rec2[f];
    vec.emplace_back(x);
    tmp.emplace_back(x);
    for (auto y:adj[x]){
        if (y==f||vis[y]) continue;
        dfs(y,x);siz[x]+=siz[y];
    }
}
void calc(int x){
    rec1[x]=rec2[x]=rec=a[x];
    vec={x};getans({x},-1);
    for (auto y:adj[x]){
        if (vis[y]) continue;
        tmp.clear();dfs(y,x);
        getans(tmp,-1);
    } getans(vec,1);
}
void solve(int x){
    vis[x]=1;calc(x);
    for (auto y:adj[x]){
        if (vis[y]) continue;
        Min=sum=siz[y];findroot(y,x);solve(rt);
    }
}
void Solve(){ int n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=n;i++) adj[i].clear(),vis[i]=0;
    for (int i=1;i<n;i++){
        int x=read(),y=read();
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    } ans=0;
    Min=sum=n;findroot(1,0);solve(rt);
    printf("%lld\n",ans);
}
int main(){int T=read();while (T--) Solve();return 0;}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10016kb

input:

2
3
1 10 100
1 2
3 2
5
1 1 1 1 1
1 2
1 3
1 4
1 5

output:

0
6

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 166ms
memory: 10044kb

input:

34763
19
98 27 61 17 77 9 97 23 24 5 94 61 100 88 98 43 8 75 96
4 17
12 17
7 3
19 4
12 5
1 18
10 5
7 2
1 4
2 11
19 9
18 16
1 11
17 15
6 3
16 8
15 14
15 13
9
49 4 97 14 1 11 52 84 84
1 3
6 4
9 7
2 6
7 8
1 2
3 8
5 9
19
92 74 62 54 60 78 74 6 76 80 13 94 4 86 85 89 23 46 2
6 17
1 8
8 2
8 14
13 7
12 9
1...

output:

135
22
128
132
148
107
9
5
122
4
1
113
23
5
15
60
54
16
24
145
14
63
122
2
32
70
2
125
2
160
0
5
128
74
130
15
70
114
33
92
146
151
14
87
8
63
31
9
82
10
13
35
19
0
144
0
18
0
24
21
60
157
73
1
5
130
33
110
20
55
19
24
51
90
16
45
16
24
13
1
63
159
12
19
73
89
15
142
83
5
45
163
21
103
35
117
10
28
...

result:

ok 34763 lines

Test #3:

score: 0
Accepted
time: 210ms
memory: 9928kb

input:

24286
23
877 532 121 81 687 796 904 979 93 712 828 161 866 704 298 51 237 983 924 202 730 615 326
16 6
5 19
16 9
13 10
16 21
19 22
10 20
2 23
18 4
17 9
23 21
3 19
21 10
8 20
1 15
1 10
20 5
16 18
7 21
14 8
9 12
13 11
24
304 993 567 447 471 201 919 544 652 998 475 918 153 388 935 53 259 889 700 342 52...

output:

199
217
211
40
138
57
22
69
255
208
159
292
127
245
165
68
14
83
2
122
133
292
75
288
257
9
131
136
11
324
143
343
128
30
31
72
20
165
36
265
57
282
8
134
251
154
338
0
80
65
334
292
232
21
45
78
156
23
6
218
335
25
1
7
94
274
308
157
66
0
5
78
168
310
11
186
87
14
104
92
69
336
2
363
18
3
129
91
27...

result:

ok 24286 lines

Test #4:

score: 0
Accepted
time: 93ms
memory: 9992kb

input:

53323
8
4 48 40 98 62 85 66 42
4 6
2 7
8 7
4 7
1 7
3 7
5 7
6
24 20 19 9 7 99
5 6
6 4
1 2
6 3
2 6
6
97 6 52 57 2 7
2 3
6 3
5 3
3 4
6 1
10
50 5 40 15 71 75 99 83 67 27
10 2
9 5
1 10
4 10
10 3
10 8
7 5
10 6
5 10
8
66 63 66 50 37 11 35 20
1 3
2 1
1 4
8 1
5 1
7 6
7 1
6
90 94 72 44 10 38
5 3
3 1
3 2
5 4
6...

output:

16
0
3
21
17
6
18
10
5
1
30
14
10
12
3
7
3
5
18
1
5
3
2
12
16
24
13
1
13
10
0
8
5
24
10
2
2
6
14
15
19
4
8
27
4
12
2
3
2
4
35
25
3
4
11
7
4
8
8
9
15
16
20
4
15
5
3
9
10
3
11
4
34
8
9
4
15
10
22
10
9
3
26
9
0
0
10
2
16
14
12
4
6
22
7
6
7
10
2
1
20
2
28
2
15
4
33
21
10
22
22
6
12
25
7
3
24
3
6
8
5
3
1...

result:

ok 53323 lines

Test #5:

score: 0
Accepted
time: 1191ms
memory: 10228kb

input:

717
147
19067 27655 2908 26474 11068 81636 48333 12988 62387 74426 8774 17796 36220 774 77734 26097 52954 55909 23250 38739 15795 17276 69234 8639 48402 66578 56241 54894 75492 65360 73728 75070 15739 97224 62547 27312 1614 21227 32738 39336 18551 96753 64074 54513 84595 37109 61162 16342 98150 6408...

output:

10392
103756
126073
204967
13047
170220
414398
7454
85119
445772
164936
146009
329931
216726
323444
5280
31559
6791
22092
449559
147003
105600
268153
11060
118644
137078
179044
497320
168978
173679
179527
5247
479624
104970
334826
290541
135967
238290
335721
370898
210187
39282
112966
201368
20319
2...

result:

ok 717 lines

Test #6:

score: -100
Time Limit Exceeded

input:

7
69369
626676 9738474 5959848 7283711 402336 1530515 5163533 6190777 4056057 5798962 5716235 6787673 6086922 9509443 449439 900898 7658590 7102057 47367 7643957 8469384 4223211 4772166 2751901 2519196 1075889 5604131 5011140 2762803 6924619 3067178 914683 5533547 7582698 738985 4509686 3833317 7930...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 00:41:48 | 开源项目