QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261643#6448. Blazing New TrailsZhouShang#AC ✓3776ms26236kbC++142.0kb2023-11-23 05:48:022023-11-23 05:48:03

Judging History

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

  • [2023-11-23 05:48:03]
  • 评测
  • 测评结果：AC
  • 用时：3776ms
  • 内存：26236kb
查看
  • [2023-11-23 05:48:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(s) (int)(x).size()
#define PB push_back
#define cmx(x, y) x = max(x, y)
#define cmn(x, y) x = min(x, y)
typedef pair<int, int> pii;
typedef vector<int> vi;
int f[200005];
int x[500005],y[500005],w[500005],id[500005],tw[500005],fa[500005];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
signed main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    int n,m,k,tar;
    cin>>n>>m>>k>>tar;
    for(int i=1,x;i<=k;i++) cin>>x,f[x]=1;
    for(int i=1;i<=m;i++) cin>>x[i]>>y[i]>>w[i],id[i]=i;
    int l=-1e12,r=1e12;
    while(l<=r){
        int mid=(l+r)/2;
        for(int i=1;i<=m;i++){
            if(f[x[i]]+f[y[i]]==1) tw[i]=w[i]+mid;
            else tw[i]=w[i];
        }
        //for(int i=1;i<=m;i++) cout<<tw[i]<<'\n';
        for(int i=1;i<=n;i++) fa[i]=i;
        sort(id+1,id+m+1,[&](int a,int b){
            return tw[a]<tw[b]||tw[a]==tw[b]&&(f[x[a]]+f[y[a]])%2<(f[x[b]]+f[y[b]])%2;
        });
        int wt=0,cl=0,cnt=0;
        for(int i=1;i<=m;i++){
            int xx=find(x[id[i]]),yy=find(y[id[i]]);
            if(xx!=yy) fa[yy]=xx,wt+=tw[id[i]],cl+=(f[x[id[i]]]+f[y[id[i]]])%2,cnt++;
        }
        if(cnt!=n-1){
            cout<<"-1\n";
            return 0;
        }
        sort(id+1,id+m+1,[&](int a,int b){
            return tw[a]<tw[b]||tw[a]==tw[b]&&(f[x[a]]+f[y[a]])%2>(f[x[b]]+f[y[b]])%2;
        });
        for(int i=1;i<=n;i++) fa[i]=i;
        int cr=0;
        for(int i=1;i<=m;i++){
            int xx=find(x[id[i]]),yy=find(y[id[i]]);
            if(xx!=yy) fa[yy]=xx,cr+=(f[x[id[i]]]+f[y[id[i]]])%2;
        }
        if(cl<=tar&&tar<=cr){
            cout<<wt-tar*mid<<'\n';
            return 0;
        }
        //cout<<mid<<" "<<cl<<" "<<cr<<'\n';
        if(tar<cl) l=mid+1;
        else r=mid-1;
    }
    cout<<"-1\n";
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3 1 2
2
1 2 2
1 3 1
2 3 3

output:

5

result:

ok single line: '5'

Test #2:

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

input:

3 1 1 1
2
1 2 2

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

3 3 1 1
2
1 2 1
1 3 1
2 3 1

output:

2

result:

ok single line: '2'

Test #4:

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

input:

3 3 1 2
2
1 2 1
1 3 1
2 3 1

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 1ms
memory: 13832kb

input:

3 3 1 1
2
1 2 1
1 3 10
2 3 1

output:

11

result:

ok single line: '11'

Test #6:

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

input:

6 9 3 1
2
4
6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #7:

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

input:

6 9 3 2
2
4
6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #8:

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

input:

6 9 3 3
2
4
6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #9:

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

input:

6 9 3 4
2
4
6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #10:

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

input:

6 9 3 5
2
4
6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1

output:

-1

result:

ok single line: '-1'

Test #11:

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

input:

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

output:

23

result:

ok single line: '23'

Test #12:

score: 0
Accepted
time: 1ms
memory: 13744kb

input:

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

output:

22

result:

ok single line: '22'

Test #13:

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

input:

6 15 3 1
2
4
6
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
2 3 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1
3 6 1
4 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #14:

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

input:

6 15 3 2
2
4
6
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
2 3 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1
3 6 1
4 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #15:

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

input:

6 15 3 3
2
4
6
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
2 3 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1
3 6 1
4 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #16:

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

input:

6 15 3 4
2
4
6
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
2 3 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1
3 6 1
4 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #17:

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

input:

6 15 3 5
2
4
6
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
2 3 1
2 4 1
2 5 1
2 6 1
3 4 1
3 5 1
3 6 1
4 5 1
4 6 1
5 6 1

output:

5

result:

ok single line: '5'

Test #18:

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

input:

11 55 5 2
2
4
6
8
10
1 2 2
1 3 2
1 4 2
1 5 2
1 6 3
1 7 1
1 8 2
1 9 3
1 10 2
1 11 1
2 3 3
2 4 3
2 5 2
2 6 2
2 7 1
2 8 3
2 9 1
2 10 1
2 11 1
3 4 1
3 5 1
3 6 1
3 7 3
3 8 1
3 9 1
3 10 2
3 11 2
4 5 3
4 6 3
4 7 1
4 8 1
4 9 2
4 10 1
4 11 2
5 6 3
5 7 3
5 8 1
5 9 3
5 10 2
5 11 2
6 7 1
6 8 3
6 9 3
6 10 3
6 11...

output:

11

result:

ok single line: '11'

Test #19:

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

input:

11 55 5 5
2
4
6
8
10
1 2 1
1 3 3
1 4 3
1 5 2
1 6 3
1 7 3
1 8 2
1 9 1
1 10 2
1 11 2
2 3 3
2 4 3
2 5 3
2 6 2
2 7 2
2 8 1
2 9 2
2 10 3
2 11 3
3 4 1
3 5 1
3 6 3
3 7 1
3 8 2
3 9 3
3 10 1
3 11 3
4 5 1
4 6 3
4 7 3
4 8 3
4 9 3
4 10 2
4 11 2
5 6 3
5 7 2
5 8 3
5 9 1
5 10 2
5 11 2
6 7 1
6 8 1
6 9 2
6 10 1
6 11...

output:

11

result:

ok single line: '11'

Test #20:

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

input:

11 55 5 8
2
4
6
8
10
1 2 3
1 3 1
1 4 1
1 5 1
1 6 2
1 7 1
1 8 3
1 9 2
1 10 3
1 11 3
2 3 1
2 4 1
2 5 2
2 6 3
2 7 3
2 8 2
2 9 1
2 10 1
2 11 1
3 4 1
3 5 2
3 6 2
3 7 1
3 8 2
3 9 1
3 10 3
3 11 3
4 5 3
4 6 3
4 7 3
4 8 1
4 9 1
4 10 3
4 11 2
5 6 3
5 7 1
5 8 3
5 9 3
5 10 2
5 11 3
6 7 1
6 8 1
6 9 2
6 10 2
6 11...

output:

10

result:

ok single line: '10'

Test #21:

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

input:

93 2668 48 63
3
5
6
8
9
10
11
13
17
20
23
24
27
29
30
32
33
34
36
37
38
40
42
45
46
48
50
52
54
55
56
58
59
61
65
67
69
70
71
74
75
78
83
85
86
89
90
93
1 2 60
1 3 93
1 4 68
1 9 60
1 11 93
1 12 87
1 14 97
1 17 83
1 19 92
1 23 53
1 24 80
1 25 87
1 29 66
1 30 54
1 31 68
1 32 56
1 33 52
1 34 86
1 35 88...

output:

4662

result:

ok single line: '4662'

Test #22:

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

input:

59 1500 31 16
2
3
4
5
6
8
12
14
17
18
19
20
22
23
24
25
30
33
34
35
37
38
39
41
49
52
53
55
57
58
59
1 2 79
1 3 94
1 4 84
1 5 63
1 6 64
1 7 52
1 8 55
1 9 96
1 10 96
1 11 54
1 13 71
1 14 51
1 15 61
1 16 85
1 18 81
1 20 59
1 21 62
1 22 71
1 24 100
1 25 100
1 26 58
1 27 85
1 28 68
1 29 83
1 30 69
1 31 ...

output:

2964

result:

ok single line: '2964'

Test #23:

score: 0
Accepted
time: 6ms
memory: 13880kb

input:

81 3077 38 34
3
7
11
13
14
15
16
17
20
24
25
31
33
34
37
38
40
43
46
47
49
50
51
52
55
57
58
60
61
62
63
67
68
70
71
75
77
78
1 2 77
1 3 51
1 4 89
1 5 68
1 7 97
1 8 80
1 9 94
1 10 92
1 11 86
1 12 85
1 13 56
1 14 65
1 15 79
1 16 96
1 18 51
1 19 62
1 20 51
1 21 62
1 22 84
1 23 84
1 24 51
1 25 62
1 26 ...

output:

4027

result:

ok single line: '4027'

Test #24:

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

input:

78 1812 42 59
2
3
6
7
9
11
12
13
14
15
16
18
19
20
21
22
26
30
32
33
35
43
47
50
51
52
55
57
59
60
62
63
64
65
66
68
72
73
74
75
76
78
1 2 78
1 3 82
1 4 60
1 5 82
1 6 84
1 7 54
1 8 69
1 11 95
1 12 94
1 15 57
1 17 84
1 18 55
1 20 65
1 21 63
1 22 67
1 23 77
1 24 60
1 25 91
1 26 74
1 27 80
1 29 55
1 30...

output:

3929

result:

ok single line: '3929'

Test #25:

score: 0
Accepted
time: 655ms
memory: 26156kb

input:

770 209687 382 602
2
4
5
6
7
9
11
12
15
17
20
21
22
29
31
32
33
36
37
39
40
41
45
46
47
49
50
51
57
58
59
60
61
62
63
65
67
68
69
71
73
74
75
76
79
83
84
85
86
88
89
91
92
95
97
99
101
103
104
105
106
108
109
112
113
115
117
118
119
122
123
125
133
134
138
140
142
145
148
149
151
152
153
154
155
156...

output:

385167

result:

ok single line: '385167'

Test #26:

score: 0
Accepted
time: 1203ms
memory: 24072kb

input:

877 356506 442 36
3
4
12
15
17
19
20
22
25
27
28
29
30
35
38
40
42
47
50
51
53
54
55
59
61
66
67
71
72
74
76
77
81
85
86
87
88
90
91
92
94
95
96
97
99
100
101
105
106
107
109
112
115
117
119
120
121
123
124
128
130
131
132
133
135
137
141
143
148
149
151
152
154
160
165
167
168
171
172
173
176
177
1...

output:

438702

result:

ok single line: '438702'

Test #27:

score: 0
Accepted
time: 443ms
memory: 17916kb

input:

612 158072 306 78
3
8
10
11
12
13
14
16
18
19
20
21
22
23
27
34
35
36
38
39
41
43
46
49
53
56
58
59
60
62
64
66
67
68
69
70
72
77
79
80
81
82
83
84
88
92
93
94
96
98
99
100
102
105
106
110
112
113
120
121
123
124
128
131
134
135
137
138
139
140
146
150
151
160
162
166
170
173
175
179
180
183
185
188...

output:

306280

result:

ok single line: '306280'

Test #28:

score: 0
Accepted
time: 607ms
memory: 26236kb

input:

850 199191 420 791
1
2
5
10
12
13
14
16
21
24
28
29
31
32
34
36
37
41
42
43
44
45
46
47
49
56
60
63
68
73
75
77
78
79
84
87
92
94
95
96
98
100
105
113
114
118
121
124
128
129
131
132
133
134
135
136
137
138
141
142
144
145
148
150
152
155
156
159
163
164
165
166
168
169
171
172
173
174
176
177
179
1...

output:

425898

result:

ok single line: '425898'

Test #29:

score: 0
Accepted
time: 92ms
memory: 24112kb

input:

2562 381580 1283 398
1
4
5
6
7
8
10
11
12
16
17
19
20
21
22
23
27
29
31
35
36
37
41
42
44
45
47
48
49
51
57
59
60
62
63
64
69
70
71
73
81
84
86
88
89
93
94
95
98
99
100
105
106
107
110
112
115
120
123
125
128
131
132
134
135
136
137
140
141
143
145
146
147
149
153
155
156
157
158
161
163
164
165
168...

output:

2561

result:

ok single line: '2561'

Test #30:

score: 0
Accepted
time: 89ms
memory: 26132kb

input:

4311 361323 2150 3208
1
3
6
7
8
9
11
12
13
14
16
19
25
26
27
28
31
33
35
37
41
44
46
47
49
52
53
54
55
56
58
61
62
63
64
65
68
71
72
78
79
80
81
82
83
84
88
92
93
95
97
98
100
101
102
103
105
107
109
112
113
114
115
117
119
120
123
127
128
129
130
131
133
134
137
138
143
150
151
154
156
157
159
162
...

output:

4310

result:

ok single line: '4310'

Test #31:

score: 0
Accepted
time: 102ms
memory: 24104kb

input:

2973 390460 1487 2737
2
5
8
11
14
21
23
27
29
31
32
33
37
38
40
41
42
43
50
52
55
57
60
61
62
65
66
68
69
71
72
73
76
77
79
80
81
82
83
84
88
89
93
94
95
96
98
101
104
106
107
109
110
111
114
116
118
120
122
125
127
128
129
130
131
132
133
135
137
138
140
141
142
144
145
146
149
152
154
156
157
158
...

output:

2972

result:

ok single line: '2972'

Test #32:

score: 0
Accepted
time: 1789ms
memory: 24152kb

input:

4636 493477 2317 4552
1
4
5
11
12
14
15
19
22
23
24
25
27
28
31
32
37
38
40
41
42
43
45
46
50
53
54
58
60
62
64
67
69
70
74
75
85
86
88
90
91
92
93
94
95
96
100
102
104
106
108
109
111
112
117
118
120
121
122
123
124
126
130
131
132
133
134
135
137
138
139
140
142
144
145
146
149
152
153
156
157
158...

output:

234188010

result:

ok single line: '234188010'

Test #33:

score: 0
Accepted
time: 1040ms
memory: 24144kb

input:

4484 278767 2246 2416
9
13
15
16
19
20
23
24
25
31
35
37
39
41
48
49
51
53
54
56
57
58
61
65
66
68
69
70
75
76
77
78
80
82
85
86
89
92
93
95
97
98
102
107
108
109
110
111
115
118
119
120
121
122
123
129
130
132
133
135
136
137
138
141
142
144
145
146
147
149
150
152
153
154
155
157
158
159
161
163
1...

output:

226319909

result:

ok single line: '226319909'

Test #34:

score: 0
Accepted
time: 2417ms
memory: 25028kb

input:

94366 446336 47187 79374
4
5
6
7
8
11
12
14
19
21
22
23
26
29
31
32
33
38
39
40
42
45
46
50
52
53
55
57
58
63
64
66
67
69
70
73
74
75
78
80
81
83
84
86
87
88
89
90
91
93
95
97
98
99
101
102
104
111
114
116
117
119
121
122
125
126
127
128
129
130
131
137
138
139
140
145
146
148
151
153
154
155
156
15...

output:

1658012229

result:

ok single line: '1658012229'

Test #35:

score: 0
Accepted
time: 2150ms
memory: 24704kb

input:

63735 407083 31869 22697
4
7
8
9
11
15
16
19
23
24
25
26
30
31
32
33
34
36
38
40
42
44
47
48
49
53
54
58
59
61
62
63
64
65
66
67
75
77
80
81
82
84
87
88
89
90
91
94
98
99
100
101
102
105
107
108
109
110
113
114
115
120
121
125
126
129
130
132
134
135
138
139
141
143
145
146
149
150
153
155
157
160
1...

output:

6316016080

result:

ok single line: '6316016080'

Test #36:

score: 0
Accepted
time: 86ms
memory: 25756kb

input:

100000 330953 50001 74127
4
10
13
15
17
18
19
20
21
22
23
24
25
27
30
32
33
34
35
36
37
38
39
44
45
48
49
50
52
53
54
56
58
59
60
62
68
69
72
73
75
76
77
80
82
84
87
89
94
95
96
98
99
103
105
106
107
108
109
110
111
115
116
119
121
123
124
126
127
129
131
132
133
136
137
139
140
141
145
146
147
148
...

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0
Accepted
time: 3514ms
memory: 24928kb

input:

100000 497336 50001 2818
1
3
6
8
9
11
12
14
15
16
18
19
20
23
24
26
27
28
30
33
34
36
38
40
41
43
44
45
46
48
49
50
51
53
55
57
62
63
65
68
70
71
79
80
81
82
84
87
88
92
97
99
103
104
108
109
110
114
115
116
119
123
125
127
129
130
132
133
138
139
142
143
144
145
146
148
151
152
153
154
157
158
160
...

output:

9999093332

result:

ok single line: '9999093332'

Test #38:

score: 0
Accepted
time: 3776ms
memory: 24916kb

input:

100000 500000 50004 61123
3
5
7
8
10
14
15
17
18
19
20
21
23
25
26
27
30
35
37
38
39
43
46
47
48
51
52
54
57
58
62
64
69
70
72
74
75
76
77
82
88
92
96
98
102
103
105
108
109
113
114
116
117
121
122
123
124
128
132
134
135
137
138
140
141
142
143
144
145
146
148
153
156
158
160
161
163
170
172
173
17...

output:

9998991085

result:

ok single line: '9998991085'

Test #39:

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

input:

6 8 3 4
2
4
6
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1

output:

-1

result:

ok single line: '-1'

Test #40:

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

input:

6 7 3 4
2
4
6
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1
4 6 1

output:

-1

result:

ok single line: '-1'
English 繁體中文 简体中文

Server Time: 2024-12-02 15:24:18 | OpenSource Project