QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200977#7343. Bicycle RaceDreamOnTL 13ms11552kbC++233.4kb2023-10-05 02:43:012023-10-05 17:21:45

Judging History

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

  • [2023-10-05 17:21:45]
  • 管理员手动重测该提交记录
  • 测评结果:TL
  • 用时:13ms
  • 内存:11552kb
  • [2023-10-05 02:43:01]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while('0' <= c && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

#define Maxn 100005
#define Maxm 100005
#define ULL unsigned long long
#define LL long long
#define L 300
#define MP(x, y) make_pair(x, y)
#define pii pair < LL, int >

struct Edge {
    int next, to, dis;
}
edge[Maxm * 2];
int head[Maxn], deg[Maxn], edge_num;
int n, m, U[Maxm], V[Maxm], D[Maxm];
int bigVer[Maxn], bigCnt; bool isBig[Maxn];

void add_edge(int from, int to, int dis) {
    edge[++edge_num].next = head[from];
    edge[edge_num].to = to;
    edge[edge_num].dis = dis;
    head[from] = edge_num;
}

map < pii, int > ind;
vector < pii > tri[Maxn];
int cmp(pii x, pii y) {
    return x.second > y.second;
}

void addCir(int u, int v, int w) {
    if(u > v) swap(u, v); if(v > w) swap(v, w); if(u > v) swap(u, v); // u < v < w
    int sum = D[ind[MP(u, v)]] + D[ind[MP(v, w)]] + D[ind[MP(w, u)]];
    tri[u].push_back(MP(v * 1e5 + w, sum));
    tri[v].push_back(MP(u * 1e5 + w, sum));
    tri[w].push_back(MP(u * 1e5 + v, sum));
}
bool noRepeat(pii e1, pii e2) {
    int u1 = e1.first / 100000, v1 = e1.first % 100000;
    int u2 = e2.first / 100000, v2 = e2.first % 100000;
    int cnt = 0;
    cnt = (u1 == u2) + (u1 == v2) + (v1 == u2) + (v1 == v2);
    if(cnt) return 0;
    else return 1;
}

void find() {
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= bigCnt; ++j) {
            int w = bigVer[j];
            if(w == U[i] || w == V[i]) continue;
            if(isBig[U[i]] && U[i] > w) continue;
            if(isBig[V[i]] && V[i] > w) continue;
            if(ind.find(MP(U[i], w)) != ind.end() && ind.find(MP(V[i], w)) != ind.end()) addCir(U[i], V[i], w);
        }
    }
    for(int i = 1; i <= m; ++i) {
        if(!isBig[U[i]] && !isBig[V[i]]) {
            for(int e = head[U[i]]; e; e = edge[e].next) {
                int w = edge[e].to;
                if(w <= U[i] || w <= V[i] || isBig[w]) continue;
                if(ind.find(MP(V[i], w)) != ind.end()) addCir(U[i], V[i], w);
            }
        }
    }
}

int main() {
    n = read(); m = read();
    for(int i = 1; i <= m; ++i) {
        U[i] = read(); V[i] = read(); D[i] = read();
        add_edge(U[i], V[i], D[i]); add_edge(V[i], U[i], D[i]);
        ind[make_pair(U[i], V[i])] = ind[make_pair(V[i], U[i])] = i;
        ++deg[U[i]]; ++deg[V[i]];
    }
    for(int i = 1; i <= n; ++i) {
        if(deg[i] >= L) bigVer[++bigCnt] = i, isBig[i] = 1;
    }

    find();
    
    int ans = -1;
    for(int x = 1; x <= n; ++x) { // Fix a vertex first
        sort(tri[x].begin(), tri[x].end(), cmp);
        for(int i = 0; i < min((int)(tri[x].size()), 16); ++i) {
            for(int j = i + 1; j < tri[x].size(); ++j) {
                pii e1 = tri[x][i], e2 = tri[x][j];
                if(noRepeat(e1, e2)) {
                    int sum = e1.second + e2.second;
                    if(sum <= ans) break;
                    else ans = sum;
                }
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

詳細信息

Test #1:

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

input:

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

output:

18

result:

ok 1 number(s): "18"

Test #2:

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

input:

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

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

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

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

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

output:

43

result:

ok 1 number(s): "43"

Test #5:

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

input:

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

output:

46

result:

ok 1 number(s): "46"

Test #6:

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

input:

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

output:

45

result:

ok 1 number(s): "45"

Test #7:

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

input:

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

output:

41

result:

ok 1 number(s): "41"

Test #8:

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

input:

200 2000
182 97 91166
25 11 25393
179 58 43378
77 41 75588
139 96 94145
135 56 4609
190 159 47293
100 30 33854
21 132 93072
174 135 93547
144 137 81216
199 102 68247
89 155 53788
83 25 64607
166 179 44534
101 3 1474
37 106 57970
187 41 19892
16 76 32024
182 13 32061
72 69 5823
187 185 13918
151 86 3...

output:

552426

result:

ok 1 number(s): "552426"

Test #9:

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

input:

400 4000
102 372 24346
360 153 94255
272 316 33427
215 71 52304
368 202 60854
350 206 16796
32 372 31489
109 14 95840
163 71 79896
330 393 95303
324 110 13216
197 341 69668
54 241 46100
222 246 67388
140 13 539
272 79 22065
389 221 81398
187 122 60482
198 352 4291
196 14 18220
215 93 64141
336 54 54...

output:

545402

result:

ok 1 number(s): "545402"

Test #10:

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

input:

600 6000
270 248 73879
94 543 63116
118 174 23476
152 301 12668
597 557 27564
566 156 28983
322 585 15685
319 598 41474
506 411 50369
334 450 80707
103 83 61569
195 333 71089
219 576 54764
409 18 70169
115 296 72896
92 155 42655
542 537 4827
387 202 1071
209 15 4380
511 165 22459
485 571 94537
570 2...

output:

545966

result:

ok 1 number(s): "545966"

Test #11:

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

input:

800 8000
391 123 23412
629 133 31977
411 31 13525
489 131 89384
427 512 94273
29 506 24818
564 397 99881
528 382 3460
448 702 20841
290 156 82464
235 56 9922
192 772 88862
784 63 47076
148 591 72950
490 531 45253
263 231 63246
295 453 44608
234 683 58012
562 56 32475
671 464 90539
454 237 97128
635 ...

output:

537316

result:

ok 1 number(s): "537316"

Test #12:

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

input:

900 9000
751 713 98178
420 281 8232
734 560 50374
234 645 19566
641 65 77628
537 681 89087
561 4 33803
457 274 26277
367 372 56077
816 485 16990
425 42 67747
543 144 89573
43 230 93232
441 701 66164
801 772 31431
773 392 73541
771 535 6323
634 271 20131
429 870 52257
54 265 33619
425 148 84463
285 6...

output:

543761

result:

ok 1 number(s): "543761"

Test #13:

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

input:

1000 10000
474 791 31535
814 802 77941
268 530 73504
935 202 16680
294 563 90749
295 865 28879
881 407 92656
170 489 69207
647 539 16716
588 994 32698
450 999 67004
450 85 62626
88 759 97603
375 910 48465
855 380 62615
581 791 48023
692 533 10312
249 752 93019
229 570 80407
135 31 24826
158 458 2555...

output:

535602

result:

ok 1 number(s): "535602"

Test #14:

score: -100
Time Limit Exceeded

input:

500 100000
2 1 54424
3 1 48973
3 2 86095
4 1 76564
4 2 82172
4 3 86663
5 1 24522
5 2 37933
5 3 67602
5 4 17497
6 1 53084
6 2 41172
6 3 52523
6 4 91108
6 5 84953
7 1 594
7 2 61541
7 3 90638
7 4 34896
7 5 73592
7 6 62931
8 2 72346
8 5 16373
8 7 95438
9 1 19930
9 2 89438
9 3 2195
9 4 71744
9 5 1168
9 6...

output:


result: