Submission #1169621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169621		1bin	Wild Boar (JOI18_wild_boar)	C++20	12 / 100	257 ms	503972 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1<<17;
const int NMAX = 2005;
const ll inf = 1e18;
ll n, m, T, L, a, b, c, A[B];
vector<pair<ll, ll>> adj[NMAX];
struct path {
    ll d, u, v;
    bool operator <(const path & t)const{return d < t.d;}
};
struct node {
    path p[5];
} seg[B * 2], nd[NMAX][NMAX];

node merge(node a, node b) {
    vector<path> v;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            if (a.p[i].v != b.p[j].u) v.push_back({a.p[i].d + b.p[j].d, a.p[i].u, b.p[j].v});
    sort(all(v));
    node res = node();
    for (int i = 0; i < 5; i++) res.p[i].d = inf;
    for (auto&path : v) {
        if (path.d < res.p[0].d) res.p[0] = path;
        if (path.v != res.p[0].v) {
            if (res.p[1].d == inf) res.p[1] = path;
            else if (path.u != res.p[1].u && res.p[2].d == inf) res.p[2] = path;
        }
        if (path.u != res.p[0].u) {
            if (res.p[3].d == inf) res.p[3] = path;
            else if (path.v != res.p[3].v && res.p[4].d == inf) res.p[4] = path;
        }
    }
    return res;
}

void upd(int ix, node t) {
    ix += B;
    seg[ix] =  t;
    ix >>= 1;
    while (ix) {
        seg[ix] = merge(seg[ix * 2], seg[ix * 2 + 1]);
        ix >>= 1;
    }
    return;
}

void build() {
    memset(nd, 0x3f, sizeof(nd));
    for (int i = 1; i <= n; i++) {
        priority_queue<tuple<ll, ll, ll, ll, ll>> pq;
        auto chk = [&](ll d, int s, int u, int v, int t) -> int {
            // cout << "chk " << s << ' ' << u << ' ' << v << ' ' << t << ' ' << d << endl;
            int f = 0;
            if (nd[s][t].p[0].d > inf) nd[s][t].p[0] = {d, u, v}, f = 1;
            if (nd[s][t].p[0].v != v) {
                if (nd[s][t].p[1].d > inf) nd[s][t].p[1]= {d, u,v}, f = 1;
                else if (nd[s][t].p[1].u != u && nd[s][t].p[2].d > inf) nd[s][t].p[2] = {d, u, v}, f = 1;
            }
            if (nd[s][t].p[0].u != u) {
                if (nd[s][t].p[3].d > inf) nd[s][t].p[3]= {d, u, v}, f = 1;
                else if (nd[s][t].p[3].v != v && nd[s][t].p[4].d > inf) nd[s][t].p[4] = {d, u, v}, f = 1;
            }
            return f;
        };

        for (auto&[u, d] : adj[i]) pq.emplace(-d, i, u, i, u);
        while (pq.size()) {
            auto[d, s, u, v, x] = pq.top(); pq.pop();
            d = -d;
            if (!chk(d, s, u, v, x)) continue;
            // cout << "dist "  << s << ' ' << u << ' ' << v << ' ' << x << ' ' << d << endl;
            for (auto&[nx, p] : adj[x])
                if (nx != v) pq.emplace(-d-p, s, u, x, nx);
        }
        // cout << "-------------end----------------\n";
    }
}

void print_node(node res) {
    for (int i = 0; i < 5; i++) cout << res.p[i].d << " " << res.p[i].u << " " << res.p[i].v << "\n";
    cout << "-----------------\n";
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> T >> L;
    while (m--) {
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }
    build();

    // for (int i = 1; i <= n; i++)
    //     for (int j = 1; j <= n; j++) {
    //         cout << "Path : " << i << " to " << j << endl;
    //         for (int k = 0; k < 4; k++) cout << dist[i][j][k] << ' ' << U[i][j][k] << ' '  << V[i][j][k] << endl;
    //         cout << "\n";
    //     }

    for (int i = 1; i <= L; i++) cin >> A[i];
    for (int i = 0; i < B; i++)
        for (int j = 0; j < 5; j++) seg[B + i].p[j] = {0,5 * i + j, 5 * i + j};
    for (int i = 1; i < L; i++) seg[B + i] = nd[A[i]][A[i + 1]];
    for (int i = B - 1; i; i--) seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
    // cout << seg[1].p[0].d << endl;

    // for (int i = 1; i < L; i++) {
    //     cout << "path  "<< A[i] << ' ' << A[i + 1] << '\n';
    //
    //     for (int j = 0; j < 4; j++) cout << seg[B + i].p[j].d << ' '  << seg[B + i].p[j].u << ' ' << seg[B + i].p[j].v << endl;
    //     cout << "-------------\n";
    // }

    // auto res = seg[B + 1];
    // for (int i = 2; i < L; i++) {
    //     if (i == 3) {
    //         print_node(res);
    //         print_node(seg[B + i]);
    //         res = merge(res,seg[B + i]);
    //         print_node(res);
    //     }
    //     res = merge(res,seg[B + i]);
    // }

    // auto res= merge(seg[B + 1], seg[B + 2]);
    // print_node(seg[B + 1]);
    // print_node(seg[B + 2]);
    // print_node(res);

    while (T--) {
        int i; cin>> i;
        cin >>A[i];
        if (i > 1) upd(i - 1 , nd[A[i - 1]][A[i]]);
        if (i < L) upd(i, nd[A[i]][A[i + 1]]);
        cout << (seg[1].p[0].d == inf ? -1 : seg[1].p[0].d) << '\n';
    }
    return 0;
}

/*
5 6 1 5
1 2 8
1 3 8
1 4 8
2 5 2
3 4 6
4 5 6
2
5
1
5
2
 */

• Subtask 1: 12 / 12
• Subtask 2: 0 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38