QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#303181	#4924. 蜘蛛爬树	zyc070419	0	56ms	38304kb	C++14	2.2kb	2024-01-11 20:27:04	2024-01-11 20:27:04

Judging History

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

[2024-01-11 20:27:04]
评测

测评结果：0
用时：56ms
内存：38304kb

查看

[2024-01-11 20:27:04]
提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 3;

inline int read() {
    char ch = getchar(); int x = 0;
    while (!isdigit(ch)) {ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x;
}

inline ll Read() {
    char ch = getchar(); int x = 0;
    while (!isdigit(ch)) {ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x;
}

int n, m, T, a[N];
int depth[N], fa[N], sz[N], son[N], top[N], id[N], num;
ll dis[N];
vector< pair<int, ll> > g[N];

void dfs1(int x, int pa, int d) {
    depth[x] = d; fa[x] = pa; sz[x] = 1;
    for (auto tmp : g[x]) {
        int y = tmp.first;
        if (y == pa) continue;
        dis[y] = dis[x] + tmp.second;
        dfs1(y, x, d + 1);
        sz[x] += sz[y];
        if (sz[y] > sz[son[x]]) son[x] = y;
    }
}

void dfs2(int x, int anc) {
    top[x] = anc; id[x] = ++num;
    if (son[x]) dfs2(son[x], anc);
    for (auto tmp : g[x]) {
        int y = tmp.first;
        if (y == fa[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}

inline int LCA(int x, int y) {
    while (top[x] ^ top[y]) {
        if (depth[top[x]] < depth[top[y]]) x ^= y ^= x ^= y;
        x = fa[top[x]];
    }
    return id[x] < id[y] ? x : y;
}

inline ll get_dis(int x, int y) {
    int lca = LCA(x, y);
    return dis[x] + dis[y] - 2 * dis[lca];
}

namespace brute {
    ll ans;

    void solve() {
        ll xx, yy;
        int x, y, d;
        while (T--) {
            ans = 9e18;
            xx = Read() - 1; yy = Read() - 1;
            x = xx % n + 1;
            y = yy % n + 1;
            d = xx / n - yy / n;
            if (d < 0) d = -d;
            for (int i = 1; i <= n; ++i) ans = min(ans, get_dis(x, i) + 1ll * a[i] * d + get_dis(i, y));
            printf("%lld\n", ans);
        }
    }
}

int main() {
    n = read(); m = read(); T = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i < n; ++i) {
        int x = read(), y = read(); ll v = Read();
        g[x].push_back(make_pair(y, v));
        g[y].push_back(make_pair(x, v));
    }
    dfs1(1, 1, 1); dfs2(1, 1);
    if (n <= 5000) brute :: solve();
    return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 0ms

memory: 11512kb

input:

97 99 1000
763118300 558295517 80676328 362318619 473105413 468927175 311496507 936935430 176032966 304576040 308583326 681580095 549392233 518152994 829474320 751189715 542810029 587869244 878512027 530678371 832766129 535259635 799122942 596982955 884696876 605325753 495661541 506105495 561218313 ...

output:

-8472828247
-3235331732
-3846959318
-7871378853
-5050153911
-3335145164
-2136665529
173357088
-5208405227
-2517477006
-9903599652
-7297456374
-9045755370
3046850553
-542006414
-3220482250
-2035500001
-1178935152
-4086973007
2500610410
-5591923427
-2830242257
-4988297313
-1022011087
64747218
-4205846...

result:

wrong answer 1st lines differ - expected: '6130845802041', found: '-8472828247'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 0

Wrong Answer

Test #20:

score: 0

Wrong Answer

time: 56ms

memory: 26004kb

input:

200000 20 200000
679416469 548913625 468159997 137709609 883140368 682558021 473174374 400192350 124143873 825920417 372498686 851213321 822264481 78195915 5427143 453304163 233551905 810910186 810046144 52603791 282167184 385032797 81387991 747194790 917579656 585184539 12659388 249218417 158295502...

output:

result:

wrong answer 1st lines differ - expected: '920563165', found: ''

Subtask #4:

score: 0

Wrong Answer

Test #28:

score: 0

Wrong Answer

time: 55ms

memory: 38304kb

input:

200000 1000000000 200000
28270302 472359923 262785485 923929785 393684160 761485431 72038469 116384740 426631758 437934930 610834083 455314140 734276543 903544756 220163018 756113376 732404264 947339315 109784905 625451008 794076307 818852312 758007217 124450858 674924509 311761991 507260538 7032362...

output:

result:

wrong answer 1st lines differ - expected: '29294995135992468', found: ''

Subtask #5:

score: 0

Wrong Answer

Test #36:

score: 0

Wrong Answer

time: 36ms

memory: 24128kb

input:

199918 1000000000 199903
1496 2382 3896 3664 1177 1627 2821 4200 3074 3783 2069 4403 629 2610 4991 4074 3033 2798 4333 3501 3667 3064 663 2821 2818 458 2950 4020 2665 3578 63 4855 4941 3492 2423 4510 1489 1018 4829 1912 3133 3174 309 287 2909 4102 4296 4526 3170 3683 4960 4863 4738 2927 2405 3600 44...

output:

result:

wrong answer 1st lines differ - expected: '1352416884531', found: ''

Subtask #6:

score: 0

Wrong Answer

Test #43:

score: 0

Wrong Answer

time: 53ms

memory: 26148kb

input:

200000 1000000000 200000
81882094 47220813 43282454 17633207 52769165 4830673 31396360 64793163 9174729 36727563 71268262 24662923 40146030 1430053 62926106 30042905 1330107 81817720 98841078 87766129 51155045 23216268 79896310 66625868 87854925 42976560 86542933 28336449 34932261 19698851 584453 90...

output:

result:

wrong answer 1st lines differ - expected: '516260625003899', found: ''

Subtask #7:

score: 0

Skipped

Dependency #1:

Subtask #8:

score: 0

Skipped