QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728588#4580. Bicycle TourMeatInTheMiddle#WA 53ms19428kbC++179.7kb2024-11-09 15:29:472024-11-09 15:29:49

Judging History

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

  • [2024-11-09 15:29:49]
  • 评测
  • 测评结果：WA
  • 用时：53ms
  • 内存：19428kb
查看
  • [2024-11-09 15:29:47]
  • 提交

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;
}
源文件, 语言: C++17

详细

Test #1:

score: 0
Wrong Answer
time: 53ms
memory: 19428kb

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:

445-1 8000

result:

wrong answer 1st lines differ - expected: '4 4 5 -1 8 0 0 0', found: '445-1 8000'
English 繁體中文 简体中文

服务器时间: 2024-12-02 15:51:08 | 开源项目