QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#727787	#4580. Bicycle Tour	MeatInTheMiddle^#	WA	238ms	45868kb	C++17	9.3kb	2024-11-09 13:49:31	2024-11-09 13:49:32

Judging History

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

[2024-11-09 13:49:32]
评测

测评结果：WA
用时：238ms
内存：45868kb

查看

[2024-11-09 13:49:31]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
typedef long long ll;
typedef long double lld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int MAXSIZE = 101010;
const long long INF = 2e9 + 5;
const double EPSILON = 1e-14;
const ll DIV = 2000003;
const long double pi = 3.14159265358979323846264338327950288419716939937510L;

struct MaxSeg
{
    struct node
    {
        ll v, lz;
    };
    vector<node> tr;
    vector<ll> a;
    int n;
    void rst(int sz) { n = sz, tr.resize(sz << 2, {0, 0}), a.resize(sz + 1, 0); }
    ll init(int nd, int s, int e)
    {
        if (s == e)
            return tr[nd].v = 0;
        int m = (s + e) >> 1;
        return tr[nd].v = max(init(nd << 1, s, m), init(nd << 1 | 1, m + 1, e));
    }

    void prp(int nd, int s, int e)
    {
        if (tr[nd].lz != 0)
        {
            tr[nd].v = max(tr[nd].v, tr[nd].lz);
            if (s != e)
            {
                tr[nd << 1].lz = max(tr[nd << 1].lz, tr[nd].lz);
                tr[nd << 1 | 1].lz = max(tr[nd << 1 | 1].lz, tr[nd].lz);
            }
            tr[nd].lz = 0;
        }
    }
    void upd(int nd, int s, int e, int l, int r, ll d)
    {
        prp(nd, s, e);
        if (r < s || e < l)
            return;
        if (l <= s && e <= r)
        {
            tr[nd].lz = max(tr[nd].lz, d);
            prp(nd, s, e);
            return;
        }
        int m = (s + e) >> 1;
        upd(nd << 1, s, m, l, r, d);
        upd(nd << 1 | 1, m + 1, e, l, r, d);
        tr[nd].v = max(tr[nd << 1].v, tr[nd << 1 | 1].v);
    }
    void upd(int l, int r, ll d)
    {
        upd(1, 1, n, l, r, d);
    }
    ll qry(int nd, int s, int e, int l, int r)
    {
        prp(nd, s, e);
        if (r < s || e < l)
            return 0;
        if (l <= s && e <= r)
        {
            return tr[nd].v;
        }
        int m = (s + e) >> 1;
        return max(qry(nd << 1, s, m, l, r),
                   qry(nd << 1 | 1, m + 1, e, l, r));
    }
    ll qry(int l, int r)
    {
        return qry(1, 1, n, l, r);
    }
};
struct MinSeg
{
    struct node
    {
        ll v, lz;
    };
    vector<node> tr;
    vector<ll> a;
    int n;
    void rst(int sz) { n = sz, tr.resize(sz << 2, {INF, INF}), a.resize(sz + 1, 0); }
    ll init(int nd, int s, int e)
    {
        if (s == e)
            return tr[nd].v = INF;
        int m = (s + e) >> 1;
        return tr[nd].v = min(init(nd << 1, s, m), init(nd << 1 | 1, m + 1, e));
    }

    void prp(int nd, int s, int e)
    {
        if (tr[nd].lz != INF)
        {
            tr[nd].v = min(tr[nd].v, tr[nd].lz);
            if (s != e)
            {
                tr[nd << 1].lz = min(tr[nd << 1].lz, tr[nd].lz);
                tr[nd << 1 | 1].lz = min(tr[nd << 1 | 1].lz, tr[nd].lz);
            }
            tr[nd].lz = INF;
        }
    }
    void upd(int nd, int s, int e, int l, int r, ll d)
    {
        prp(nd, s, e);
        if (r < s || e < l)
            return;
        if (l <= s && e <= r)
        {
            tr[nd].lz = min(tr[nd].lz, d);
            prp(nd, s, e);
            return;
        }
        int m = (s + e) >> 1;
        upd(nd << 1, s, m, l, r, d);
        upd(nd << 1 | 1, m + 1, e, l, r, d);
        tr[nd].v = min(tr[nd << 1].v, tr[nd << 1 | 1].v);
    }
    void upd(int l, int r, ll d)
    {
        upd(1, 1, n, l, r, d);
    }
    ll qry(int nd, int s, int e, int l, int r)
    {
        prp(nd, s, e);
        if (r < s || e < l)
            return INF;
        if (l <= s && e <= r)
        {
            return tr[nd].v;
        }
        int m = (s + e) >> 1;
        return min(qry(nd << 1, s, m, l, r),
                   qry(nd << 1 | 1, m + 1, e, l, r));
    }
    ll qry(int l, int r)
    {
        return qry(1, 1, n, l, r);
    }
};

class HLD1
{
public:
    int sz[MAXSIZE] = {0}, dep[MAXSIZE] = {0}, par[MAXSIZE] = {0}, top[MAXSIZE] = {0}, in[MAXSIZE] = {0}, out[MAXSIZE] = {0};
    vector<int> g[MAXSIZE];
    vector<int> inp[MAXSIZE];

    MaxSeg seg;
    int chk[MAXSIZE] = {0};
    void dfs(int v = 1)
    {
        chk[v] = 1;
        for (auto i : inp[v])
        {
            if (chk[i])
                continue;
            chk[i] = 1;
            g[v].push_back(i);
            dfs(i);
        }
    }
    void dfs1(int v = 1)
    {
        sz[v] = 1;
        for (auto &i : g[v])
        {
            dep[i] = dep[v] + 1;
            par[i] = v;
            dfs1(i);
            sz[v] += sz[i];
            if (sz[i] > sz[g[v][0]])
                swap(i, g[v][0]);
        }
    }
    int pv = 0;
    void dfs2(int v = 1)
    {
        in[v] = ++pv;
        for (auto i : g[v])
        {
            top[i] = i == g[v][0] ? top[v] : i;
            dfs2(i);
        }
        out[v] = pv;
    }
    void update(int a, int b, int w)
    {
        while (top[a] ^ top[b])
        {
            if (dep[top[a]] < dep[top[b]])
                swap(a, b);
            int st = top[a];
            seg.upd(in[st], in[a], w);
            a = par[st];
        }
        if (dep[a] > dep[b])
            swap(a, b);
        seg.upd(in[a] + 1, in[b], w);
    }
    ll query(int a, int b)
    {
        ll ret = 0;
        while (top[a] ^ top[b])
        {
            if (dep[top[a]] < dep[top[b]])
                swap(a, b);
            int st = top[a];
            ret = max(ret, seg.qry(in[st], in[a]));
            a = par[st];
        }
        if (dep[a] > dep[b])
            swap(a, b);
        ret = max(ret, seg.qry(in[a] + 1, in[b]));
        return ret;
    }
};

class HLD2
{
public:
    int sz[MAXSIZE] = {0}, dep[MAXSIZE] = {0}, par[MAXSIZE] = {0}, top[MAXSIZE] = {0}, in[MAXSIZE] = {0}, out[MAXSIZE] = {0};
    vector<int> g[MAXSIZE];
    vector<int> inp[MAXSIZE];

    MinSeg seg;
    int chk[MAXSIZE] = {0};
    void dfs(int v = 1)
    {
        chk[v] = 1;
        for (auto i : inp[v])
        {
            if (chk[i])
                continue;
            chk[i] = 1;
            g[v].push_back(i);
            dfs(i);
        }
    }
    void dfs1(int v = 1)
    {
        sz[v] = 1;
        for (auto &i : g[v])
        {
            dep[i] = dep[v] + 1;
            par[i] = v;
            dfs1(i);
            sz[v] += sz[i];
            if (sz[i] > sz[g[v][0]])
                swap(i, g[v][0]);
        }
    }
    int pv = 0;
    void dfs2(int v = 1)
    {
        in[v] = ++pv;
        for (auto i : g[v])
        {
            top[i] = i == g[v][0] ? top[v] : i;
            dfs2(i);
        }
        out[v] = pv;
    }

    void update(int a, int b, int w)
    {
        while (top[a] ^ top[b])
        {
            if (dep[top[a]] < dep[top[b]])
                swap(a, b);
            int st = top[a];
            seg.upd(in[st], in[a], w);
            a = par[st];
        }
        if (dep[a] > dep[b])
            swap(a, b);

        seg.upd(in[a], in[b], w);
    }
    ll query(int a, int b)
    {
        ll ret = INF;
        while (top[a] ^ top[b])
        {
            if (dep[top[a]] < dep[top[b]])
                swap(a, b);
            int st = top[a];
            ret = min(ret, seg.qry(in[st], in[a]));
            a = par[st];
        }
        if (dep[a] > dep[b])
            swap(a, b);
        ret = min(ret, seg.qry(in[a], in[b]));
        return ret;
    }
};

int n, m;
int arr[101010];
vector<array<int, 3>> edg;
HLD1 hld1;
HLD2 hld2;

int us[101010];
int prt[101001];

int find(int x)
{
    if (prt[x] == 0 || prt[x] == x)
        return prt[x] = x;
    return prt[x] = find(prt[x]);
}

void mrg(int a, int b)
{
    prt[find(a)] = find(b);
}

int main()
{
    fastio;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i + 1];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        edg.push_back({abs(arr[a] - arr[b]), a, b});
    }

    sort(edg.begin(), edg.end());
    hld2.seg.rst(n + 5); // ans
    hld1.seg.rst(n + 5); //

    for (int i = 0; i < m; i++)
    {
        int d = edg[i][0], a = edg[i][1], b = edg[i][2];
        if (find(a) == find(b))
            continue;

        mrg(a, b);

        us[i] = 1;
        hld1.inp[a].push_back(b);
        hld1.inp[b].push_back(a);

        hld2.inp[a].push_back(b);
        hld2.inp[b].push_back(a);
    }
    hld1.dfs();
    hld1.dfs1();
    hld1.dfs2();

    hld2.dfs();
    hld2.dfs1();
    hld2.dfs2();
    for (int i = 0; i < m; i++)
    {
        if (us[i])
        {
            int d = edg[i][0], a = edg[i][1], b = edg[i][2];
            hld1.update(a, b, d);
        }
    }

    for (int i = 0; i < m; i++)
    {
        if (!us[i])
        {
            int d = edg[i][0], a = edg[i][1], b = edg[i][2];
            int mx = hld1.query(a, b);
            hld2.update(a, b, d);
        }
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        int t = hld2.query(i, i);
        if (t >= INF)
            ans.push_back(-1);
        else
            ans.push_back(t);
    }
    for (int i : ans)
    {
        cout << i << " ";
    }

    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 18576kb

input:

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

output:

4 4 5 -1 8 0 0 0

result:

ok single line: '4 4 5 -1 8 0 0 0 '

Test #2:

score: 0

Accepted

time: 0ms

memory: 18936kb

input:

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

output:

20 20 20 30

result:

ok single line: '20 20 20 30 '

Test #3:

score: 0

Accepted

time: 0ms

memory: 18608kb

input:

5 4
72 35 22 49 108
1 2
2 3
3 4
4 5

output:

-1 -1 -1 -1 -1

result:

ok single line: '-1 -1 -1 -1 -1 '

Test #4:

score: 0

Accepted

time: 3ms

memory: 18944kb

input:

2 1
10 20
1 2

output:

-1 -1

result:

ok single line: '-1 -1 '

Test #5:

score: 0

Accepted

time: 17ms

memory: 18864kb

input:

252 31626
825 5234 3578 4723 2145 4362 1861 2413 7203 1939 3210 7153 2155 4559 4403 1466 887 3786 6529 719 4272 3287 5703 6708 2390 4987 4214 770 3487 6230 3498 6255 4963 1093 3065 2961 1663 4857 3224 4284 4228 106 1614 1010 145 1557 4510 1032 4632 155 5570 154 884 1204 2876 6163 5023 4593 7261 3729...

output:

55 33 46 34 10 33 34 30 22 33 33 46 10 34 26 100 14 62 17 9 13 35 81 45 23 29 23 20 11 32 11 32 29 38 18 13 14 0 28 13 11 42 35 22 9 57 22 22 35 7 52 7 14 45 72 92 14 8 15 62 10 20 21 34 66 9 20 24 29 6 30 16 26 9 6 27 8 40 85 17 12 26 29 17 10 61 35 9 39 15 14 14 31 22 63 66 110 24 16 7 30 22 15 18...

result:

ok single line: '55 33 46 34 10 33 34 30 22 33 ...5 15 71 10 52 18 16 30 10 34 4 '

Test #6:

score: 0

Accepted

time: 2ms

memory: 18652kb

input:

30 435
268435456 1024 67108864 16777216 134217728 131072 524288 512 256 8 32 64 33554432 2097152 128 2048 16384 8192 4096 8388608 65536 536870912 4 2 16 1048576 32768 1 262144 4194304
24 28
23 28
10 28
25 28
11 28
12 28
15 28
9 28
8 28
2 28
16 28
19 28
18 28
17 28
27 28
21 28
6 28
28 29
7 28
26 28
1...

output:

201326592 768 50331648 12582912 100663296 98304 393216 384 192 6 24 48 25165824 1572864 96 1536 12288 6144 3072 6291456 49152 402653184 3 3 12 786432 24576 3 196608 3145728

result:

ok single line: '201326592 768 50331648 1258291... 786432 24576 3 196608 3145728 '

Test #7:

score: 0

Accepted

time: 45ms

memory: 19912kb

input:

430 92235
268435456 64 536870912 256 128 134217728 2 64 33554432 524288 1048576 268435456 1048576 512 32 32 8192 8192 8192 268435456 256 1024 16384 8 2097152 1 4 65536 268435456 32768 2048 512 128 32768 268435456 8192 4194304 16384 1024 4194304 128 33554432 67108864 1 512 16 128 16384 536870912 4 16...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '

Test #8:

score: 0

Accepted

time: 238ms

memory: 21972kb

input:

4815 185773
999998072 999997632 999995973 999998063 999999530 999999125 999999430 999998145 999999596 999997846 999999214 999998642 999997013 999995796 999999311 999996273 999996607 999996332 999995768 999996225 999996086 999996362 999997090 999997081 999998960 999996645 999996842 999998514 99999527...

output:

66 57 91 47 76 25 193 80 42 120 47 87 36 50 34 219 43 42 97 227 57 40 28 45 141 46 111 84 164 131 99 60 135 181 88 44 147 58 104 199 60 202 24 46 53 56 116 105 79 48 26 34 59 79 52 31 131 166 29 38 35 25 146 119 275 33 42 119 84 95 32 57 280 106 92 47 309 116 52 310 47 85 100 53 114 35 23 84 79 70 7...

result:

ok single line: '66 57 91 47 76 25 193 80 42 12...173 79 85 50 80 71 47 22 56 49 '

Test #9:

score: -100

Wrong Answer

time: 222ms

memory: 45868kb

input:

98999 135802
999915141 999970725 999970117 999947993 999935245 999995293 999929471 999931920 999920419 999957183 999935027 999960800 999906092 999915777 999965089 999905949 999979021 999933691 999988435 999975097 999960084 999972032 999910145 999932210 999933979 999910318 999926596 999961902 9999664...

output:

-1 26917 -1 -1 38445 -1 29312 -1 -1 27742 -1 40947 -1 -1 -1 34789 -1 -1 33543 -1 26917 -1 29995 40427 30208 44827 41060 31384 -1 -1 29692 -1 25703 31337 -1 40560 21511 26288 -1 -1 32090 34373 40241 -1 37436 -1 -1 -1 41333 -1 30032 35731 -1 33762 -1 -1 24201 -1 39997 46526 39063 24242 -1 37486 -1 296...

result:

wrong answer 1st lines differ - expected: '67767 26917 -1 -1 38445 72454 ...4 77902 30701 65641 47833 85899', found: '-1 26917 -1 -1 38445 -1 29312 ...922 35544 -1 30701 -1 47833 -1 '