QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51161#277. Beads and wiresBaltinic100 ✓39ms18760kbC++2.9kb2022-10-01 10:45:012022-10-01 10:45:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-01 10:45:04]
  • 评测
  • 测评结果:100
  • 用时:39ms
  • 内存:18760kb
  • [2022-10-01 10:45:01]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<iostream>
using std::cerr;
namespace IO{
    char buf[1<<15],*fs,*ft;
    inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
    inline int read(){
        int x=0,rev=0,ch=getc();
        while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getc();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getc();}
        return rev?-x:x;
    }
}using namespace IO;
const int MAXN(200000),D(50),INF(1<<30);
struct edge{
    int y,l,next;
}e[MAXN*2+D];
int head[MAXN+D];
inline void connect(int x,int y,int l){
    static int k=0;
    e[++k].next=head[x];e[head[x]=k].y=y;e[k].l=l;
    e[++k].next=head[y];e[head[y]=k].y=x;e[k].l=l;
}
int n,root,ans=-INF;
int f[MAXN+D][2],sum[MAXN+D],maxd[MAXN+D][2],len[MAXN+D];
void init(){
    n=read();root=1;
    for(int i=1;i<n;i++){
        int x=read(),y=read(),l=read();
        connect(x,y,l);
    }
}
inline int max(int a,int b){return a>b?a:b;}
int stack[MAXN+D],top;
int par[MAXN+D];
bool oped[MAXN+D];
void dp(){
    oped[stack[top=1]=root]=false;
    while(top){
        int x=stack[top];
        if(oped[x]){
            maxd[x][0]=maxd[x][1]=-INF;
            for(int i=head[x],y;i;i=e[i].next)
                if((y=e[i].y)!=par[x]){
                    int temp=max(e[i].l+f[y][1],f[y][0]);
                    f[x][0]+=temp;
                    temp=e[i].l+f[y][0]-temp;
                    if(temp>maxd[x][0])
                        maxd[x][1]=maxd[x][0],maxd[x][0]=temp;
                    else if(temp>maxd[x][1])
                        maxd[x][1]=temp;
                }
            f[x][1]=f[x][0]+maxd[x][0];
            top--;
        }
        else{
            oped[x]=true;
            for(int i=head[x],y;i;i=e[i].next)
                if((y=e[i].y)!=par[x]){
                    par[y]=x;
                    len[y]=e[i].l;
                    oped[stack[++top]=y]=false;
                }
        }
    }
}
void dfs(int x){
    int old0=maxd[x][0],old1=maxd[x][1],olf0=f[x][0],olf1=f[x][1];
    if(x!=root){
        int temp=max(len[x]+f[par[x]][1],f[par[x]][0]);
        f[x][0]+=temp;
        temp=len[x]+f[par[x]][0]-temp;
        if(temp>maxd[x][0])
            maxd[x][1]=maxd[x][0],maxd[x][0]=temp;
        else if(temp>maxd[x][1])
            maxd[x][1]=temp;
    }
    ans=max(ans,f[x][0]);
    for(int i=head[x],y;i;i=e[i].next)
        if((y=e[i].y)!=par[x]){
            int t0=f[x][0],t1=f[x][1];
            int temp=max(e[i].l+f[y][1],f[y][0]);
            f[x][0]-=temp;
            temp=e[i].l+f[y][0]-temp;
            f[x][1]=f[x][0]+(temp==maxd[x][0]?maxd[x][1]:maxd[x][0]);
            dfs(y);
            f[x][0]=t0;f[x][1]=t1;
        }
    maxd[x][0]=old0;maxd[x][1]=old1;
    f[x][0]=olf0;f[x][1]=olf1;
}
int main(){
    init();
    dp();
    dfs(root);
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 4ms
memory: 7796kb

input:

5
1 2 10
1 3 40
1 4 15
1 5 20

output:

60

result:

ok single line: '60'

Test #2:

score: 0
Accepted
time: 3ms
memory: 7776kb

input:

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

output:

140

result:

ok single line: '140'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7760kb

input:

10
4 10 5
1 10 7
3 10 10
3 9 10
2 3 5
3 8 9
7 10 3
5 8 9
4 6 6

output:

61

result:

ok single line: '61'

Test #4:

score: 0
Accepted
time: 3ms
memory: 7760kb

input:

10
7 10 1
2 7 3
6 7 5
1 9 5
5 7 3
2 3 3
3 4 3
2 9 5
6 8 3

output:

30

result:

ok single line: '30'

Test #5:

score: 0
Accepted
time: 3ms
memory: 7756kb

input:

10
3 10 6
3 7 6
8 9 3
1 5 1
2 10 4
4 10 2
1 8 6
1 10 10
6 9 7

output:

44

result:

ok single line: '44'

Test #6:

score: 0
Accepted
time: 2ms
memory: 7688kb

input:

10
5 6 9
2 3 5
1 10 8
4 5 9
2 7 8
5 7 10
6 9 4
2 8 9
1 7 5

output:

62

result:

ok single line: '62'

Test #7:

score: 0
Accepted
time: 2ms
memory: 7824kb

input:

10
2 3 7
6 9 7
2 10 6
4 9 2
2 8 5
1 6 1
6 7 10
6 8 9
2 5 6

output:

41

result:

ok single line: '41'

Test #8:

score: 0
Accepted
time: 2ms
memory: 7776kb

input:

10
7 9 1
3 5 9
1 6 3
5 9 3
5 8 10
6 10 9
2 5 3
2 4 10
8 10 6

output:

53

result:

ok single line: '53'

Test #9:

score: 0
Accepted
time: 3ms
memory: 7748kb

input:

10
3 6 9
2 5 5
2 4 1
4 9 2
5 7 7
2 10 3
5 6 10
1 2 6
5 8 3

output:

43

result:

ok single line: '43'

Test #10:

score: 0
Accepted
time: 0ms
memory: 7684kb

input:

10
2 3 4
4 8 9
1 8 2
2 4 6
4 5 7
4 7 4
2 10 6
4 9 1
6 7 1

output:

39

result:

ok single line: '39'

Test #11:

score: 0
Accepted
time: 3ms
memory: 7696kb

input:

10
1 8 4
2 3 7
3 10 4
2 4 7
6 7 5
3 7 7
7 9 10
5 9 6
3 8 2

output:

48

result:

ok single line: '48'

Test #12:

score: 0
Accepted
time: 0ms
memory: 7784kb

input:

10
8 9 7
2 3 8
2 6 5
2 9 1
2 10 3
5 9 3
4 5 3
7 8 9
1 2 2

output:

35

result:

ok single line: '35'

Subtask #2:

score: 15
Accepted

Test #13:

score: 15
Accepted
time: 2ms
memory: 7808kb

input:

100
48 93 4
12 87 1
27 72 10
3 43 2
33 86 2
37 80 8
51 98 4
34 57 3
5 51 7
15 100 9
41 72 4
14 30 10
27 80 7
50 71 7
6 77 6
36 66 1
47 61 2
71 92 7
20 94 7
3 59 1
55 69 7
16 33 5
71 79 6
18 96 4
4 43 3
1 55 4
65 75 10
82 96 2
30 74 9
12 19 6
46 93 1
83 94 9
22 24 1
27 51 9
33 92 4
25 42 10
71 81 8
3...

output:

441

result:

ok single line: '441'

Test #14:

score: 0
Accepted
time: 3ms
memory: 7832kb

input:

100
38 97 8
26 29 9
62 73 7
13 62 8
6 63 3
22 82 9
57 90 10
34 40 10
86 87 6
62 72 8
35 67 4
24 47 10
14 60 9
43 92 4
85 91 1
56 62 5
57 69 6
30 45 8
69 92 5
15 99 1
6 78 9
64 89 1
20 88 8
66 92 2
31 63 4
31 70 8
42 79 2
11 59 2
9 97 6
24 62 8
8 21 9
84 100 7
4 50 10
54 63 5
24 98 10
2 97 1
4 25 3
2...

output:

498

result:

ok single line: '498'

Test #15:

score: 0
Accepted
time: 3ms
memory: 7772kb

input:

100
13 54 5
7 94 5
9 39 7
52 53 8
9 80 9
23 45 2
41 63 1
66 94 2
35 70 1
15 35 1
60 66 1
11 46 3
46 79 2
8 70 7
8 29 7
70 75 10
8 77 10
11 36 8
14 45 10
12 24 1
8 73 3
1 23 10
12 86 5
8 72 3
28 74 8
63 69 5
7 49 6
5 19 4
23 37 3
19 83 1
10 59 7
56 78 10
54 82 10
4 88 8
7 8 10
22 51 4
8 97 3
21 35 10...

output:

460

result:

ok single line: '460'

Test #16:

score: 0
Accepted
time: 0ms
memory: 7796kb

input:

200
147 182 33
101 186 14
7 66 10
73 180 33
43 130 36
130 166 5
20 23 48
1 148 5
43 49 12
20 104 20
27 53 41
71 124 39
21 123 39
44 200 24
18 25 46
17 38 11
48 144 49
22 126 7
57 153 12
96 124 39
18 126 40
28 134 35
15 87 16
43 75 44
129 157 28
75 143 14
12 104 9
57 128 50
107 153 7
68 174 15
20 163...

output:

4537

result:

ok single line: '4537'

Test #17:

score: 0
Accepted
time: 3ms
memory: 7700kb

input:

200
33 93 17
63 114 24
19 93 42
151 168 9
78 84 30
17 60 27
81 115 10
108 185 24
85 189 12
39 129 23
7 84 6
169 177 31
30 70 42
21 56 45
65 112 47
63 74 16
19 29 41
69 115 21
49 92 37
39 174 26
57 91 39
26 170 23
4 12 49
59 134 26
19 143 41
90 146 13
25 99 38
141 147 14
27 47 23
10 141 22
49 76 35
7...

output:

4605

result:

ok single line: '4605'

Test #18:

score: 0
Accepted
time: 2ms
memory: 7832kb

input:

200
25 94 45
143 166 19
24 103 16
133 200 43
39 45 40
100 113 35
99 189 41
127 131 33
107 136 33
34 40 22
63 66 13
43 170 47
9 160 9
7 10 40
6 168 19
45 78 39
48 133 46
94 111 41
3 183 6
84 198 45
56 160 15
110 152 17
50 53 50
75 76 43
36 143 12
83 176 44
124 174 16
26 96 33
73 118 42
48 188 8
8 139...

output:

4695

result:

ok single line: '4695'

Test #19:

score: 0
Accepted
time: 0ms
memory: 7764kb

input:

200
74 191 24
74 171 19
2 74 50
27 74 42
8 74 45
74 89 33
74 182 46
74 168 34
9 74 9
37 74 11
74 106 48
74 81 30
74 185 38
56 74 30
74 98 46
74 167 14
74 110 12
74 134 15
74 102 38
74 144 32
35 74 29
42 74 14
20 74 24
62 74 18
50 74 9
19 74 48
74 94 41
22 74 41
74 193 22
74 147 43
74 141 42
28 74 15...

output:

546

result:

ok single line: '546'

Test #20:

score: 0
Accepted
time: 0ms
memory: 7828kb

input:

200
98 200 12
12 87 47
19 98 31
9 87 14
61 87 18
98 189 24
26 98 8
42 98 42
130 192 22
34 192 7
98 167 28
105 192 24
98 188 40
37 98 17
155 192 15
63 98 28
98 139 23
14 192 10
45 98 38
98 172 44
98 146 43
75 87 35
98 116 26
98 165 41
87 171 14
87 150 9
11 192 14
46 98 29
192 198 14
98 176 25
80 192 ...

output:

233

result:

ok single line: '233'

Test #21:

score: 0
Accepted
time: 3ms
memory: 7876kb

input:

200
47 130 8
25 47 15
47 172 33
6 47 45
47 64 50
28 164 17
47 123 35
164 195 19
43 150 30
47 66 5
47 54 47
47 138 40
3 175 39
47 185 34
47 97 22
149 164 43
32 47 28
1 47 35
47 137 17
47 124 13
164 192 38
42 47 19
20 47 7
47 180 18
47 145 24
47 176 13
120 191 11
47 52 37
33 47 26
41 164 28
126 164 37...

output:

1202

result:

ok single line: '1202'

Test #22:

score: 0
Accepted
time: 2ms
memory: 7800kb

input:

200
56 174 43
28 56 22
26 112 21
56 119 44
56 139 36
29 113 25
7 63 44
10 66 32
96 182 44
56 136 17
56 103 41
9 95 48
118 138 23
18 56 39
21 177 49
8 56 32
22 69 39
25 84 10
82 146 10
19 56 42
149 153 40
80 89 12
11 56 41
140 195 11
38 56 44
122 181 47
65 150 29
56 106 18
43 75 40
84 193 44
56 127 1...

output:

3349

result:

ok single line: '3349'

Subtask #3:

score: 29
Accepted

Test #23:

score: 29
Accepted
time: 4ms
memory: 7940kb

input:

5000
2198 4992 964
2521 2711 961
3408 4585 975
2746 3304 974
2514 3411 972
602 4079 952
1193 3742 996
774 4530 942
2234 3877 905
346 1537 959
886 3841 937
3126 3342 938
211 2423 977
1725 4740 944
2125 4020 961
1235 3070 903
3109 4669 970
3923 4815 972
2525 4784 979
1159 1511 968
1900 3573 960
2087 2...

output:

3848169

result:

ok single line: '3848169'

Test #24:

score: 0
Accepted
time: 0ms
memory: 8020kb

input:

5000
1926 2920 933
565 1093 993
1894 4373 930
1713 3978 916
2318 4827 999
2151 2951 984
227 1132 931
4454 4935 962
287 3086 920
1228 3395 997
2598 3601 988
2630 4017 972
489 3089 988
1120 2369 910
1965 4008 902
2799 2962 945
580 3947 965
477 1954 911
692 2334 932
1785 2113 940
2627 3908 970
3803 415...

output:

3789162

result:

ok single line: '3789162'

Test #25:

score: 0
Accepted
time: 2ms
memory: 7896kb

input:

5000
2488 4286 905
898 3460 995
3342 4660 963
38 1300 971
1608 4845 980
667 987 986
1297 3504 908
14 4515 975
1158 3753 965
2445 4021 994
3156 4046 928
848 2888 944
196 3340 955
1029 2200 929
1910 2338 967
903 4235 911
1178 3515 905
2139 2800 936
2616 4819 984
541 1777 930
1050 4535 917
421 2932 929...

output:

3818444

result:

ok single line: '3818444'

Test #26:

score: 0
Accepted
time: 0ms
memory: 8024kb

input:

10000
2751 6467 4918
3158 3563 4945
3261 6833 4929
2955 6313 4923
2546 5953 4970
87 4008 4926
4233 9238 4957
5579 6868 4908
1661 1837 4905
495 5863 4997
1757 7978 4995
4242 6106 4990
1531 5173 4952
7667 9651 4953
4615 8041 4950
1115 4959 4965
2536 5619 4911
8543 9472 4975
3423 8796 4915
2168 7691 49...

output:

40189502

result:

ok single line: '40189502'

Test #27:

score: 0
Accepted
time: 0ms
memory: 7960kb

input:

10000
2180 7493 4923
5745 9205 4949
446 7909 4938
2787 8203 4921
1605 6768 4959
5895 8634 4996
4304 5699 4953
3330 5057 4908
4894 7534 4922
4738 6264 4982
1687 8362 4906
7398 8058 5000
7867 9913 4968
2527 3617 4906
2417 6827 4951
4556 8870 4979
2732 3225 4941
772 2389 4939
4521 6696 4922
532 7737 49...

output:

40070133

result:

ok single line: '40070133'

Test #28:

score: 0
Accepted
time: 4ms
memory: 8040kb

input:

10000
3748 4584 4926
3748 7419 4990
1194 3748 4924
3748 6181 4996
2894 3748 4944
1529 3748 5000
3748 4208 4944
1112 3748 4924
898 3748 4922
3748 6970 4949
3748 8935 4910
3748 9738 4907
3066 3748 4904
3205 3748 4935
2444 3748 4974
3748 7430 4907
3748 9707 4936
2618 3748 4972
3748 8642 4913
3748 4468 ...

output:

3991669

result:

ok single line: '3991669'

Test #29:

score: 0
Accepted
time: 2ms
memory: 7984kb

input:

10000
1070 4104 4988
2982 3086 4963
7216 8547 4971
1070 7973 4941
1070 8162 4955
1070 6364 4996
7482 8547 4951
1070 4704 4985
1070 4573 4957
3118 8547 4959
1070 2922 4959
1070 6773 4978
1622 8547 4991
3086 9569 4912
3086 7803 4954
6442 8547 4998
1070 5174 5000
3086 4231 4981
3086 6495 4988
1070 6452...

output:

29901

result:

ok single line: '29901'

Test #30:

score: 0
Accepted
time: 2ms
memory: 8120kb

input:

10000
7902 8933 4901
3764 6085 4995
1621 3537 4934
4050 8356 4996
8356 8367 4979
3764 4865 4943
1209 8356 4982
3764 4875 4915
8169 8933 4946
7498 8933 4934
8356 8491 4922
4360 8933 4989
3388 3764 4964
3764 5553 4972
3764 9678 4978
3764 6485 4971
3764 9365 4981
2374 8933 4960
3764 4294 4994
2393 8933...

output:

8971361

result:

ok single line: '8971361'

Test #31:

score: 0
Accepted
time: 4ms
memory: 8408kb

input:

10000
3309 7441 4960
5499 9949 4978
339 5089 4928
4076 7951 4916
8352 9949 4914
3172 9949 4927
9297 9949 4902
465 1921 4901
6918 9949 4980
4214 9949 4962
770 1130 4903
2983 4158 4946
3632 6635 4909
8184 8691 4922
1361 1487 4991
4992 5555 4957
2373 9949 4986
9198 9403 4915
6062 9949 4917
4831 9514 49...

output:

29562255

result:

ok single line: '29562255'

Subtask #4:

score: 43
Accepted

Test #32:

score: 43
Accepted
time: 7ms
memory: 8652kb

input:

50000
22758 25880 990
917 25140 901
10537 30620 913
10368 14209 993
40077 48077 900
5064 20728 937
39641 39844 906
819 11079 965
12203 41474 993
13965 27792 923
20713 39385 991
4266 46545 938
27293 40442 937
12696 27693 961
10394 24153 998
24393 26653 926
25825 32799 963
33049 38343 946
15252 41731 ...

output:

38479584

result:

ok single line: '38479584'

Test #33:

score: 0
Accepted
time: 5ms
memory: 8696kb

input:

50000
3238 13619 998
16363 38824 982
27886 39526 947
11705 35966 934
32675 34385 905
22609 46082 942
7299 14249 915
6399 15810 989
11836 44016 903
4399 46581 923
12715 33309 954
4238 16794 968
37297 41894 986
9139 43847 954
2500 26308 955
14692 47635 909
9024 20555 911
23428 26653 944
43468 48679 93...

output:

38503542

result:

ok single line: '38503542'

Test #34:

score: 0
Accepted
time: 5ms
memory: 9620kb

input:

50000
35799 44598 957
11590 25577 939
4784 35538 999
5004 9994 968
22358 35054 973
6448 27238 933
10516 41720 950
11755 11835 924
17441 23218 941
1328 34075 987
28738 40598 984
10901 21323 936
16548 29610 943
14617 41939 975
19028 49172 1000
22990 40282 938
36368 43770 914
38947 40691 981
2730 9343 ...

output:

38465202

result:

ok single line: '38465202'

Test #35:

score: 0
Accepted
time: 36ms
memory: 14140kb

input:

200000
30736 178178 9996
90079 171554 9980
25124 79152 9901
54905 96160 9925
29000 54206 9931
74835 155568 9978
74889 140509 9928
52105 197486 9925
111197 172841 9974
4714 76829 9983
1973 78283 9954
13818 196042 9965
48033 105703 9958
116361 141539 9999
124735 182083 9988
10938 91743 9940
39395 1762...

output:

1605459774

result:

ok single line: '1605459774'

Test #36:

score: 0
Accepted
time: 39ms
memory: 14044kb

input:

200000
108342 138357 9984
110960 113525 9938
41108 45029 9990
55734 141188 9963
34485 95051 9948
48613 82260 9952
69962 158318 9913
9086 40837 9984
67630 177377 9902
86309 117483 9978
74833 137014 9986
58515 115876 9980
66845 142345 9946
79325 151532 9953
1579 91728 9923
59877 99166 9998
180352 1857...

output:

1607393503

result:

ok single line: '1607393503'

Test #37:

score: 0
Accepted
time: 29ms
memory: 14048kb

input:

200000
126722 130360 9943
89278 168087 9902
119299 167497 9901
53594 131583 9919
20469 43852 9970
83614 197327 9935
85332 113486 9982
10302 29961 9997
103964 191999 9907
66701 174284 9989
34958 129858 9972
16022 196923 9957
13887 38193 9965
108706 118465 9938
140685 151024 9951
124806 194312 9997
27...

output:

1606037984

result:

ok single line: '1606037984'

Test #38:

score: 0
Accepted
time: 24ms
memory: 15148kb

input:

200000
164755 181587 9909
108623 181587 9979
322 181587 9974
181138 181587 9946
20490 181587 9958
27152 181587 9908
90143 181587 9953
103487 181587 9901
93671 181587 9909
17523 181587 9929
150951 181587 9936
25906 181587 9959
104826 181587 9947
34144 181587 9935
77429 181587 9900
40960 181587 9999
1...

output:

160485772

result:

ok single line: '160485772'

Test #39:

score: 0
Accepted
time: 22ms
memory: 14524kb

input:

200000
27257 170181 9998
27257 46336 9911
64710 109131 9958
47607 164375 9999
27257 99191 9916
109131 126015 9996
27257 116762 9905
27257 82704 9932
97542 109131 9945
478 109131 9990
57748 109131 9929
86498 109131 9997
159340 164375 9975
109131 109234 9908
109131 131360 9959
109131 131412 9967
17057...

output:

59979

result:

ok single line: '59979'

Test #40:

score: 0
Accepted
time: 19ms
memory: 14436kb

input:

200000
100383 177661 9902
29890 102857 9905
4153 102857 9990
42390 177661 9901
15819 78137 9945
111862 177661 9908
116351 172954 9997
116351 149438 9925
100033 116351 9984
19469 102857 9996
102857 132996 9934
116351 129422 9915
115349 177661 9952
57372 177661 9972
102857 196263 9998
33426 90594 9945...

output:

360716635

result:

ok single line: '360716635'

Test #41:

score: 0
Accepted
time: 29ms
memory: 18760kb

input:

200000
122137 172111 9908
53871 122137 9978
85117 168845 9993
3821 9227 9906
58661 78687 9960
2352 126484 9908
6663 14567 9986
122137 198958 9952
77627 168280 9948
63324 122137 9984
122137 188498 9984
40323 199355 9961
52160 60985 9979
23933 122137 9907
4073 154064 9978
37834 68699 9969
50083 122137...

output:

1183642659

result:

ok single line: '1183642659'