Submission #1252507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252507		duckindog	Wild Boar (JOI18_wild_boar)	C++20	100 / 100	3005 ms	381744 KiB

wild_boar

#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 10,
			L = 100'000 + 10;
int n, m, q, l;
vector<pair<int, int>> ad[N];
int x[L];

struct Path { 
    int a, b;
    long long dist;
    Path(int a = 0, int b = 0, long long dist = 0) : a(a), b(b), dist(dist) {}
    bool operator < (const Path& rhs) const { 
        return dist < rhs.dist;
    }
};

const int SZ = 5;
struct Node { 
    vector<Path> vt;

    bool insert(const Path& add) { 
        if ((int)vt.size() == SZ) return false;
        
        bool mkA = false, mkB = false;
        for (const auto& [a, b, dist] : vt) { 
            if (a == add.a && b == add.b) return false;
            if (a == add.a) { 
                if (mkA) return false;
                mkA = true;
            }
            if (b == add.b) { 
                if (mkB) return false;
                mkB = true;
            }
        }

        vt.push_back(add);
        return true;
    }
} path[N][N];

Node merge(const Node& lt, const Node& rt) { 
    Node ret;

    vector<Path> proc;
    for (const auto& [aL, bL, distL] : lt.vt) { 
        for (const auto& [aR, bR, distR] : rt.vt) {
            if (bL != aR) proc.push_back(Path(aL, bR, distL + distR));
        }
    }
    sort(proc.begin(), proc.end());
    for (const auto& path : proc) ret.insert(path);

    return ret;
}

Node f[L << 2];
void build(int s, int l, int r) { 
    if (l == r) { 
        f[s] = path[x[l]][x[l + 1]];
        return;
    }
    int mid = (l + r) >> 1;
    build(s << 1, l, mid);
    build(s << 1 | 1, mid + 1, r);
    f[s] = merge(f[s << 1], f[s << 1 | 1]);
}
void update(int s, int l, int r, int p) { 
    if (l == r) { 
        f[s] = path[x[l]][x[l + 1]];
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(s << 1, l, mid, p);
    else update(s << 1 | 1, mid + 1, r, p);
    f[s] = merge(f[s << 1], f[s << 1 | 1]);
}
inline long long query() { 
    return !f[1].vt.size() ? -1 : f[1].vt[0].dist;
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q >> l;
    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        ad[u].push_back({v, w});
        ad[v].push_back({u, w});
    }
    for (int i = 1; i <= l; ++i) cin >> x[i];

    for (int i = 1; i <= n; ++i) { // dijsktra
        using TP = tuple<long long, int, int, int>;
        priority_queue<TP, vector<TP>, greater<>> pq;
        for (const auto& [v, w] : ad[i]) pq.emplace(w, v, i, v);
        
        while (pq.size()) { 
            auto [d, s, p, u] = pq.top(); pq.pop();
            if (!path[i][u].insert(Path(s, p, d))) continue;
            for (const auto& [v, w] : ad[u]) { 
                if (v != p) pq.emplace(d + w, s, u, v);
            }
        }
    }

    build(1, 1, l - 1);
    while (q--) { 
        int p; cin >> p >> x[p];
    
        if (p) update(1, 1, l - 1, p - 1);
        if (p < l) update(1, 1, l - 1, p);

        cout << query() << "\n";
    }
}

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