Submission #131928

#	Time	Username	Problem	Language	Result	Execution time	Memory
131928		imeimi2000	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	4066 ms	526180 KiB

wild_boar

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
const llong inf = 1e18;
int n, m, T, L;
 
struct _edge {
    int x, c, i;
    _edge(int x, int c, int i) : x(x), c(c), i(i) {}
};
vector<_edge> edge[2001];
int a[2000];
int b[2000];
int c[2000];
llong dist[4000][2001][2];
int used[4000][2001][2];
 
struct pqNode {
    int x, t;
    llong c;
    pqNode(int x, int t, llong c) : x(x), t(t), c(c) {}
    bool operator<(const pqNode &p) const {
        return c > p.c;
    }
};
 
void dijkstra(int se, llong dist[2001][2], int used[2001][2]) {
    for (int i = 1; i <= n; ++i) {
        dist[i][0] = inf;
        dist[i][1] = inf;
        used[i][0] = -1;
        used[i][1] = -1;
    }
    int s = (se & 1) ? a[se >> 1] : b[se >> 1];
    priority_queue<pqNode> pq;
    pq.emplace(s, used[s][0] = (se >> 1), dist[s][0] = c[se >> 1]);
    while (!pq.empty()) {
        pqNode x = pq.top();
        pq.pop();
        if (used[x.x][0] != x.t && used[x.x][1] != x.t) continue;
        if (used[x.x][0] == x.t && dist[x.x][0] != x.c) continue;
        if (used[x.x][1] == x.t && dist[x.x][1] != x.c) continue;
        for (_edge i : edge[x.x]) {
            if ((i.i >> 1) == x.t) continue;
            llong d = x.c + i.c;
            if (d < dist[i.x][0]) {
                dist[i.x][1] = dist[i.x][0];
                used[i.x][1] = used[i.x][0];
                
                pq.emplace(i.x, used[i.x][0] = (i.i >> 1), dist[i.x][0] = d);
            }
            else if (used[i.x][0] != (i.i >> 1) && d < dist[i.x][1]) {
                pq.emplace(i.x, used[i.x][1] = (i.i >> 1), dist[i.x][1] = d);
            }
        }
    }    
}
 
struct _distData {
    int sx, ex;
    llong c;
    _distData() : c(inf) {}
    _distData(int sx, int ex, llong c)
        : sx(sx), ex(ex), c(c) {}
    _distData operator+(const _distData &x) const {
        if (ex == x.sx) return _distData();
        llong d = c + x.c;
        if (inf <= d) return _distData();
        return _distData(sx, x.ex, d);
    }
};
 
struct distData {
    _distData x[5];
    void push(int i, _distData p) {
        if (i == 0) {
            if (p.c < x[0].c) x[0] = p;
        }
        else if (i == 1) {
            if (p.sx == x[0].sx) return;
            if (p.c < x[1].c) x[1] = p;
        }
        else if (i == 2) {
            if (p.sx == x[0].sx) return;
            if (p.ex == x[1].ex) return;
            if (p.c < x[2].c) x[2] = p;
        }
        else if (i == 3) {
            if (p.ex == x[0].ex) return;
            if (p.c < x[3].c) x[3] = p;
        }
        else {
            if (p.ex == x[0].ex) return;
            if (p.sx == x[3].sx) return;
            if (p.c < x[4].c) x[4] = p;
        }
    }
    void merge(const distData &a, const distData &b) {
        for (int i = 0; i < 5; ++i) x[i] = _distData();
        static _distData v[25];
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                v[5 * i + j] = a.x[i] + b.x[j];
            }
        }
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 25; ++j) {
                push(i, v[j]);
            }
        }
    }
} dst[2001][2001], seg[1 << 18];
int xs[100001];
 
void init(int i, int s, int e) {
    if (s + 1 == e) {
        seg[i] = dst[xs[s]][xs[e]];
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m, e);
    seg[i].merge(seg[i << 1], seg[i << 1 | 1]);
}
 
void update(int i, int s, int e, int x) {
    if (s + 1 == e) {
        seg[i] = dst[xs[s]][xs[e]];
        return;
    }
    int m = (s + e) / 2;
    if (x < m) update(i << 1, s, m, x);
    else update(i << 1 | 1, m, e, x);
    seg[i].merge(seg[i << 1], seg[i << 1 | 1]);
}
 
int main() {
    scanf("%d%d%d%d", &n, &m, &T, &L);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", a + i, b + i, c + i);
        edge[a[i]].emplace_back(b[i], c[i], i << 1);
        edge[b[i]].emplace_back(a[i], c[i], i << 1 | 1);
    }
    for (int i = 0; i < (m << 1); ++i) {
        dijkstra(i, dist[i], used[i]);
    }
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < (m << 1); ++j) {
            int s = (j & 1) ? b[j >> 1] : a[j >> 1]; 
            for (int k = 1; k <= n; ++k) {
                dst[s][k].push(i, _distData(j >> 1, used[j][k][0], dist[j][k][0]));
                dst[s][k].push(i, _distData(j >> 1, used[j][k][1], dist[j][k][1]));
            }
        }
    }
    for (int i = 1; i <= L; ++i) {
        scanf("%d", xs + i);
    }
    
    init(1, 1, L);
    
    for (int i = 0; i < T; ++i) {
        int p, q;
        scanf("%d%d", &p, &q);
        xs[p] = q;
        if (p < L) update(1, 1, L, p);
        if (p > 1) update(1, 1, L, p - 1);
        llong ans = seg[1].x[0].c;
        printf("%lld\n", ans < inf ? ans : -1);
    }
	return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:155:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &T, &L);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", a + i, b + i, c + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", xs + i);
         ~~~~~^~~~~~~~~~~~~~
wild_boar.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &p, &q);
         ~~~~~^~~~~~~~~~~~~~~~

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