QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#830022#2893. 独立lyxAC ✓10ms8804kbC++144.7kb2024-12-24 15:29:392024-12-24 15:29:43

Judging History

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

  • [2024-12-24 15:29:43]
  • 评测
  • 测评结果：AC
  • 用时：10ms
  • 内存：8804kb
查看
  • [2024-12-24 15:29:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define dep(i, u, d) for(int i = u; i >= d; --i)
#define cep(n) while(n--)
#define gep(i, a) for(int i = firs[a]; i; i = neig[i])
int ured() {
    int ch, re = 0;

    do {
        ch = getchar();
    } while ('9' < ch || ch < '0');

    do {
        re = re * 10 + (ch ^ '0');
    } while ('0' <= (ch = getchar()) && ch <= '9');

    return re;
}
void uwit(long long da) {
    int ch[21], cn = 0;

    do {
        ch[++cn] = da - da / 10 * 10;
    } while (da /= 10);

    do {
        putchar('0' ^ ch[cn]);
    } while (--cn);
}
const int _maxn = 100011;
int n, m, q = 101, b = 137, p = 1000000007, x[_maxn], y[_maxn], a[_maxn], z[_maxn], firs[_maxn], neig[_maxn],
          arri[_maxn], valu[_maxn];
int tops, atno[_maxn], data;
long long dans, dpot[_maxn][2], rans, cans;
bool visi[_maxn], pdif;
void dfs1(int at, int fa) {
    visi[at] = 1;
    gep(i, at) {
        if (arri[i] != fa) {
            if (visi[arri[i]]) {
                if (!atno[at]) {
                    atno[at] = ++tops;
                }

                if (!atno[arri[i]]) {
                    atno[arri[i]] = ++tops;
                }
            } else {
                dfs1(arri[i], at);
            }
        }
    }
}
void dfs2(int at, int fa) {
    dpot[at][0] = dpot[at][1] = 0;

    if (atno[at]) {
        if ((data >> (atno[at] - 1)) & 1) {
            long long rg = a[at];
            gep(i, at) {
                if (arri[i] != fa) {
                    if (atno[arri[i]]) {
                        if (((data >> (atno[arri[i]] - 1)) & 1) && arri[i] < at) {
                            rg -= valu[i];
                        }
                    } else {
                        dfs2(arri[i], at);
                        dpot[at][1] = max(dpot[arri[i]][0] >= 0 ? dpot[at][1] + dpot[arri[i]][0] : -1000000000000000000,
                                          dpot[arri[i]][1] >= 0 ? dpot[at][1] + dpot[arri[i]][1] - valu[i] : -1000000000000000000);
                    }
                }
            }
            dpot[at][1] += rg;
            dpot[at][0] = -1;
        } else {
            long long rg = 0;
            gep(i, at) {
                if (arri[i] != fa) {
                    if (!atno[arri[i]]) {
                        dfs2(arri[i], at);
                        dpot[at][0] = max(dpot[arri[i]][0] >= 0 ? dpot[at][0] + dpot[arri[i]][0] : -1000000000000000000,
                                          dpot[arri[i]][1] >= 0 ? dpot[at][0] + dpot[arri[i]][1] : -1000000000000000000);
                    }
                }
            }
            dpot[at][1] = -1;
        }
    } else {
        gep(i, at) {
            if (arri[i] != fa) {
                dfs2(arri[i], at);
                dpot[at][0] = max(dpot[arri[i]][0] >= 0 ? dpot[at][0] + dpot[arri[i]][0] : -1000000000000000000,
                                  dpot[arri[i]][1] >= 0 ? dpot[at][0] + dpot[arri[i]][1] : -1000000000000000000);
                dpot[at][1] = max(dpot[arri[i]][0] >= 0 ? dpot[at][1] + dpot[arri[i]][0] : -1000000000000000000,
                                  dpot[arri[i]][1] >= 0 ? dpot[at][1] + dpot[arri[i]][1] - valu[i] : -1000000000000000000);
            }
        }
        dpot[at][1] += a[at];
    }
}
int main() {
    n = ured();
    m = ured();
    x[0] = ured();
    y[0] = ured();
    a[0] = ured();
    z[0] = ured();
    rep(i, 1, n) {
        a[i] = (1ll * q * a[i - 1] + b) % p;
    }
    rep(i, 1, m) {
        x[i] = (1ll * q * x[i - 1] + b) % p;
        y[i] = (1ll * q * y[i - 1] + b) % p;
        z[i] = (1ll * q * z[i - 1] + b) % p;
    }
    rep(i, 1, m) {
        x[i] = x[i] % n + 1;
        y[i] = y[i] % n + 1;

        if (x[i] != y[i]) {
            pdif = 1;
            gep(j, x[i]) {
                if (arri[j] == y[i]) {
                    pdif = 0;
                    break;
                }
            }

            if (pdif) {
                neig[i << 1] = firs[x[i]];
                firs[x[i]] = i << 1;
                arri[i << 1] = y[i];
                valu[i << 1] = z[i];
                neig[i << 1 | 1] = firs[y[i]];
                firs[y[i]] = i << 1 | 1;
                arri[i << 1 | 1] = x[i];
                valu[i << 1 | 1] = z[i];
            }
        }
    }
    rep(i, 1, n) {
        if (!visi[i]) {
            tops = 0;
            dfs1(i, 0);
            cans = 0;

            for (data = 0; data < (1 << tops); ++data) {
                dfs2(i, 0);
                cans = max(cans, max(dpot[i][0], dpot[i][1]));
            }

            rans += cans;
        }
    }
    uwit(rans);
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7640kb

input:

10 5 1 2 3 4

output:

3909327860

result:

ok single line: '3909327860'

Test #2:

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

input:

10000 5000 323944114 980712849 218464573 902936457

output:

4127316482561

result:

ok single line: '4127316482561'

Test #3:

score: 0
Accepted
time: 10ms
memory: 8460kb

input:

100000 50000 69108640 163256243 729156747 674884157

output:

40985622819672

result:

ok single line: '40985622819672'

Test #4:

score: 0
Accepted
time: 8ms
memory: 7908kb

input:

100000 50000 274087387 315287350 284117614 889718361

output:

40947902019309

result:

ok single line: '40947902019309'

Test #5:

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

input:

100000 50000 626549769 467318457 986562122 104552559

output:

40907099503987

result:

ok single line: '40907099503987'

Test #6:

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

input:

100000 50000 831528516 619349564 689006624 319386763

output:

41017978988200

result:

ok single line: '41017978988200'

Test #7:

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

input:

100000 50000 36507256 771380671 243967491 534220967

output:

41077280523359

result:

ok single line: '41077280523359'

Test #8:

score: 0
Accepted
time: 7ms
memory: 8152kb

input:

100000 50000 388969637 923411777 946411999 749055172

output:

41009748953373

result:

ok single line: '41009748953373'

Test #9:

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

input:

100000 50000 593948384 75442877 648856501 963889376

output:

40991206034855

result:

ok single line: '40991206034855'

Test #10:

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

input:

100000 50000 946410766 227473984 203817368 31239940

output:

40932441913184

result:

ok single line: '40932441913184'

Test #11:

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

input:

100000 50000 663698625 561638538 539101941 150346545

output:

40924699056938

result:

ok single line: '40924699056938'

Test #12:

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

input:

6 3 90677470 927115294 683528073 970379897

output:

2137516189

result:

ok single line: '2137516189'

Test #13:

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

input:

100000 50000 713669645 241546443 365180750 489471924

output:

40894915891391

result:

ok single line: '40894915891391'

Test #14:

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

input:

100000 50000 221139747 865700752 943990951 580014954

output:

40816659887937

result:

ok single line: '40816659887937'

Test #15:

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

input:

100000 50000 426118494 17731852 498951818 794849159

output:

41067804257367

result:

ok single line: '41067804257367'

Test #16:

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

input:

100000 50000 778580875 169762958 201396320 57380682

output:

41019991719429

result:

ok single line: '41019991719429'

Test #17:

score: 0
Accepted
time: 7ms
memory: 8132kb

input:

100000 50000 983559622 321794065 903840828 77033926

output:

41056783133409

result:

ok single line: '41056783133409'

Test #18:

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

input:

100000 50000 188538363 473825172 458801695 291868131

output:

40983981734650

result:

ok single line: '40983981734650'

Test #19:

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

input:

100000 50000 541000744 625856279 161246197 506702335

output:

41007858745216

result:

ok single line: '41007858745216'

Test #20:

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

input:

100000 50000 745979491 777887386 863690705 721536540

output:

41012305119617

result:

ok single line: '41012305119617'

Test #21:

score: 0
Accepted
time: 7ms
memory: 7860kb

input:

100000 50000 929918492 418651573 936370744 288067408

output:

40948033429862

result:

ok single line: '40948033429862'

Test #22:

score: 0
Accepted
time: 10ms
memory: 8348kb

input:

100000 50000 815729732 264083040 753936146 558134119

output:

41103051884986

result:

ok single line: '41103051884986'

Test #23:

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

input:

6 3 517823605 849894548 121910581 290446313

output:

2830036710

result:

ok single line: '2830036710'

Test #24:

score: 0
Accepted
time: 7ms
memory: 7840kb

input:

100000 50000 20708472 416114146 456380647 122827913

output:

41018143959974

result:

ok single line: '41018143959974'

Test #25:

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

input:

100000 50000 373170854 568145253 11341514 337662118

output:

41028863217493

result:

ok single line: '41028863217493'

Test #26:

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

input:

100000 50000 578149601 720176360 713786023 552496322

output:

40951181028791

result:

ok single line: '40951181028791'

Test #27:

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

input:

100000 50000 930611982 872207467 416230524 767330526

output:

40948576487909

result:

ok single line: '40948576487909'

Test #28:

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

input:

100000 50000 135590722 982164731 788820845 353029936

output:

41020594313888

result:

ok single line: '41020594313888'

Test #29:

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

input:

100000 50000 340569469 28786039 673635900 196998928

output:

41035989067161

result:

ok single line: '41035989067161'

Test #30:

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

input:

100000 50000 693031851 180817146 376080401 411833133

output:

41069115335862

result:

ok single line: '41069115335862'

Test #31:

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

input:

100000 50000 898010598 332848253 626667337 356729603

output:

41076889170221

result:

ok single line: '41076889170221'

Test #32:

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

input:

100000 50000 102989338 484879360 633485777 841501541

output:

41126348825706

result:

ok single line: '41126348825706'

Test #33:

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

input:

100000 50000 967760839 966527548 968770350 813124513

output:

40963659647260

result:

ok single line: '40963659647260'

Test #34:

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

input:

10 5 335727704 87288204 547385244 288081467

output:

3351218817

result:

ok single line: '3351218817'

Test #35:

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

input:

100000 50000 172739579 671214851 27958710 289574275

output:

41023167425732

result:

ok single line: '41023167425732'

Test #36:

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

input:

100000 50000 525201960 123106121 226175719 242792915

output:

40939293482589

result:

ok single line: '40939293482589'

Test #37:

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

input:

100000 50000 730180708 275137227 928620227 457627119

output:

41116772147109

result:

ok single line: '41116772147109'

Test #38:

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

input:

100000 50000 427168334 631064729 672461324 857483040

output:

41025540909037

result:

ok single line: '41025540909037'

Test #39:

score: 0
Accepted
time: 9ms
memory: 8296kb

input:

100000 50000 287621829 579199441 186025596 887295528

output:

41041606108852

result:

ok single line: '41041606108852'

Test #40:

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

input:

100000 50000 492600576 731230548 888470104 520261001

output:

41050863684028

result:

ok single line: '41050863684028'

Test #41:

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

input:

100000 50000 845062957 883261655 590914606 169480296

output:

41064379595552

result:

ok single line: '41064379595552'

Test #42:

score: 0
Accepted
time: 7ms
memory: 8216kb

input:

100000 50000 50041698 35292754 145875473 384314500

output:

40994165715249

result:

ok single line: '40994165715249'

Test #43:

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

input:

100000 50000 255020445 187323861 848319981 599148705

output:

41015913407828

result:

ok single line: '41015913407828'

Test #44:

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

input:

100000 0 1 2 3 4

output:

49891211697278

result:

ok single line: '49891211697278'

Test #45:

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

input:

100 50 499308315 298486660 933836775 591606674

output:

40654051506

result:

ok single line: '40654051506'

Test #46:

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

input:

100000 50000 1 1 2 3

output:

49965403577651

result:

ok single line: '49965403577651'

Test #47:

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

input:

100 50 85174457 766036718 917683570 796585422

output:

38414656729

result:

ok single line: '38414656729'

Test #48:

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

input:

1000 500 187537858 256543968 335220000 244298843

output:

404321266633

result:

ok single line: '404321266633'

Test #49:

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

input:

1000 500 655087915 92907130 687682381 396329949

output:

400275637877

result:

ok single line: '400275637877'

Test #50:

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

input:

10000 5000 340097318 775734102 66433466 200491948

output:

4124854860192

result:

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

Server Time: 2025-01-20 16:34:22 | OpenSource Project