oj.uz

Submission #58209

# Submission time Handle Problem Language Result Execution time Memory
58209 2018-07-17T07:28:19 Z King Suryal(#1687) Wild Boar (JOI18_wild_boar) C++11
12 / 100
 285 ms 335552 KB 
#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 = 1e16;
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][2000][2];
int used[4000][2000][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 &t) const {
        return c > t.c;
    }
};

void dijkstra(int se, llong dist[2000][2], int used[2000][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] = dist[i.x][1];
                
                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 (i == 4) {
            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(distData &a, 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 update(int i, int s, int e, int x) {
    if (s + 1 == e) {
        seg[i] = dst[xs[x]][xs[x + 1]];
        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);
    }
    for (int i = 1; i < L; ++i) {
        update(1, 1, L, i);
    }
    
    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

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:144: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:146: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:163: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:171: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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 334480 KB Output is correct
2 Correct 226 ms 334576 KB Output is correct
3 Correct 238 ms 334628 KB Output is correct
4 Correct 267 ms 334628 KB Output is correct
5 Correct 238 ms 334628 KB Output is correct
6 Correct 284 ms 334692 KB Output is correct
7 Correct 252 ms 334740 KB Output is correct
8 Correct 261 ms 334844 KB Output is correct
9 Correct 233 ms 335044 KB Output is correct
10 Correct 253 ms 335044 KB Output is correct
11 Correct 228 ms 335044 KB Output is correct
12 Correct 244 ms 335044 KB Output is correct
13 Correct 241 ms 335044 KB Output is correct
14 Correct 256 ms 335044 KB Output is correct
15 Correct 251 ms 335044 KB Output is correct
16 Correct 285 ms 335044 KB Output is correct
17 Correct 250 ms 335044 KB Output is correct
18 Correct 260 ms 335044 KB Output is correct
19 Correct 235 ms 335044 KB Output is correct
20 Correct 240 ms 335044 KB Output is correct
21 Correct 270 ms 335068 KB Output is correct
22 Correct 255 ms 335068 KB Output is correct
23 Correct 258 ms 335068 KB Output is correct
24 Correct 263 ms 335068 KB Output is correct
25 Correct 231 ms 335068 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 334480 KB Output is correct
2 Correct 226 ms 334576 KB Output is correct
3 Correct 238 ms 334628 KB Output is correct
4 Correct 267 ms 334628 KB Output is correct
5 Correct 238 ms 334628 KB Output is correct
6 Correct 284 ms 334692 KB Output is correct
7 Correct 252 ms 334740 KB Output is correct
8 Correct 261 ms 334844 KB Output is correct
9 Correct 233 ms 335044 KB Output is correct
10 Correct 253 ms 335044 KB Output is correct
11 Correct 228 ms 335044 KB Output is correct
12 Correct 244 ms 335044 KB Output is correct
13 Correct 241 ms 335044 KB Output is correct
14 Correct 256 ms 335044 KB Output is correct
15 Correct 251 ms 335044 KB Output is correct
16 Correct 285 ms 335044 KB Output is correct
17 Correct 250 ms 335044 KB Output is correct
18 Correct 260 ms 335044 KB Output is correct
19 Correct 235 ms 335044 KB Output is correct
20 Correct 240 ms 335044 KB Output is correct
21 Correct 270 ms 335068 KB Output is correct
22 Correct 255 ms 335068 KB Output is correct
23 Correct 258 ms 335068 KB Output is correct
24 Correct 263 ms 335068 KB Output is correct
25 Correct 231 ms 335068 KB Output is correct
26 Incorrect 266 ms 335552 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 334480 KB Output is correct
2 Correct 226 ms 334576 KB Output is correct
3 Correct 238 ms 334628 KB Output is correct
4 Correct 267 ms 334628 KB Output is correct
5 Correct 238 ms 334628 KB Output is correct
6 Correct 284 ms 334692 KB Output is correct
7 Correct 252 ms 334740 KB Output is correct
8 Correct 261 ms 334844 KB Output is correct
9 Correct 233 ms 335044 KB Output is correct
10 Correct 253 ms 335044 KB Output is correct
11 Correct 228 ms 335044 KB Output is correct
12 Correct 244 ms 335044 KB Output is correct
13 Correct 241 ms 335044 KB Output is correct
14 Correct 256 ms 335044 KB Output is correct
15 Correct 251 ms 335044 KB Output is correct
16 Correct 285 ms 335044 KB Output is correct
17 Correct 250 ms 335044 KB Output is correct
18 Correct 260 ms 335044 KB Output is correct
19 Correct 235 ms 335044 KB Output is correct
20 Correct 240 ms 335044 KB Output is correct
21 Correct 270 ms 335068 KB Output is correct
22 Correct 255 ms 335068 KB Output is correct
23 Correct 258 ms 335068 KB Output is correct
24 Correct 263 ms 335068 KB Output is correct
25 Correct 231 ms 335068 KB Output is correct
26 Incorrect 266 ms 335552 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 334480 KB Output is correct
2 Correct 226 ms 334576 KB Output is correct
3 Correct 238 ms 334628 KB Output is correct
4 Correct 267 ms 334628 KB Output is correct
5 Correct 238 ms 334628 KB Output is correct
6 Correct 284 ms 334692 KB Output is correct
7 Correct 252 ms 334740 KB Output is correct
8 Correct 261 ms 334844 KB Output is correct
9 Correct 233 ms 335044 KB Output is correct
10 Correct 253 ms 335044 KB Output is correct
11 Correct 228 ms 335044 KB Output is correct
12 Correct 244 ms 335044 KB Output is correct
13 Correct 241 ms 335044 KB Output is correct
14 Correct 256 ms 335044 KB Output is correct
15 Correct 251 ms 335044 KB Output is correct
16 Correct 285 ms 335044 KB Output is correct
17 Correct 250 ms 335044 KB Output is correct
18 Correct 260 ms 335044 KB Output is correct
19 Correct 235 ms 335044 KB Output is correct
20 Correct 240 ms 335044 KB Output is correct
21 Correct 270 ms 335068 KB Output is correct
22 Correct 255 ms 335068 KB Output is correct
23 Correct 258 ms 335068 KB Output is correct
24 Correct 263 ms 335068 KB Output is correct
25 Correct 231 ms 335068 KB Output is correct
26 Incorrect 266 ms 335552 KB Output isn't correct
27 Halted 0 ms 0 KB -