QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728598#4580. Bicycle TourMeatInTheMiddle#TL 57ms19628kbC++179.7kb2024-11-09 15:30:312024-11-09 15:30:33

Judging History

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

  • [2024-11-09 15:30:33]
  • 评测
  • 测评结果：TL
  • 用时：57ms
  • 内存：19628kb
查看
  • [2024-11-09 15:30: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;

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

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});
    }
    fill(ans, ans + n + 5, INF);
    sort(edg.begin(), edg.end());

    for (int y = 0; y < 55; y++)
    {
        HLD1 hld1;
        HLD2 hld2;
        memset(us, 0, sizeof us);
        memset(prt, 0, sizeof prt);
        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, max(d, mx));
            }
        }

        for (int i = 1; i <= n; i++)
        {
            int t = hld2.query(i, i);
            ans[i] = min(ans[i], t);
        }
        random_shuffle(edg.begin(), edg.end());
    }

    for (int i = 1; i <= n; i++)
    {
        if (ans[i] == INF)
            cout << -1 << " ";
        else
            cout << ans[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: 52ms
memory: 19376kb

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: 54ms
memory: 19628kb

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: 57ms
memory: 19424kb

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: 52ms
memory: 19428kb

input:

2 1
10 20
1 2

output:

-1 -1

result:

ok single line: '-1 -1 '

Test #5:

score: -100
Time Limit Exceeded

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:
English 繁體中文 简体中文

Server Time: 2024-12-02 15:54:01 | OpenSource Project