oj.uz

Submission #58212

# Submission time Handle Problem Language Result Execution time Memory
58212 2018-07-17T07:39:29 Z King Suryal(#1687) Wild Boar (JOI18_wild_boar) C++11
47 / 100
 3511 ms 523304 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][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(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 219 ms 334456 KB Output is correct
2 Correct 248 ms 334572 KB Output is correct
3 Correct 217 ms 334656 KB Output is correct
4 Correct 228 ms 334676 KB Output is correct
5 Correct 229 ms 334888 KB Output is correct
6 Correct 223 ms 334888 KB Output is correct
7 Correct 242 ms 334888 KB Output is correct
8 Correct 258 ms 334888 KB Output is correct
9 Correct 251 ms 334888 KB Output is correct
10 Correct 254 ms 334948 KB Output is correct
11 Correct 292 ms 334948 KB Output is correct
12 Correct 277 ms 334948 KB Output is correct
13 Correct 262 ms 334948 KB Output is correct
14 Correct 231 ms 334948 KB Output is correct
15 Correct 228 ms 334948 KB Output is correct
16 Correct 261 ms 334948 KB Output is correct
17 Correct 226 ms 334948 KB Output is correct
18 Correct 246 ms 334948 KB Output is correct
19 Correct 229 ms 334948 KB Output is correct
20 Correct 277 ms 334948 KB Output is correct
21 Correct 261 ms 334948 KB Output is correct
22 Correct 228 ms 334948 KB Output is correct
23 Correct 218 ms 334948 KB Output is correct
24 Correct 215 ms 334948 KB Output is correct
25 Correct 245 ms 334948 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 334456 KB Output is correct
2 Correct 248 ms 334572 KB Output is correct
3 Correct 217 ms 334656 KB Output is correct
4 Correct 228 ms 334676 KB Output is correct
5 Correct 229 ms 334888 KB Output is correct
6 Correct 223 ms 334888 KB Output is correct
7 Correct 242 ms 334888 KB Output is correct
8 Correct 258 ms 334888 KB Output is correct
9 Correct 251 ms 334888 KB Output is correct
10 Correct 254 ms 334948 KB Output is correct
11 Correct 292 ms 334948 KB Output is correct
12 Correct 277 ms 334948 KB Output is correct
13 Correct 262 ms 334948 KB Output is correct
14 Correct 231 ms 334948 KB Output is correct
15 Correct 228 ms 334948 KB Output is correct
16 Correct 261 ms 334948 KB Output is correct
17 Correct 226 ms 334948 KB Output is correct
18 Correct 246 ms 334948 KB Output is correct
19 Correct 229 ms 334948 KB Output is correct
20 Correct 277 ms 334948 KB Output is correct
21 Correct 261 ms 334948 KB Output is correct
22 Correct 228 ms 334948 KB Output is correct
23 Correct 218 ms 334948 KB Output is correct
24 Correct 215 ms 334948 KB Output is correct
25 Correct 245 ms 334948 KB Output is correct
26 Correct 222 ms 335228 KB Output is correct
27 Correct 980 ms 337372 KB Output is correct
28 Correct 931 ms 337372 KB Output is correct
29 Correct 1044 ms 341516 KB Output is correct
30 Correct 948 ms 341548 KB Output is correct
31 Correct 1006 ms 341548 KB Output is correct
32 Correct 1124 ms 341548 KB Output is correct
33 Correct 1042 ms 342176 KB Output is correct
34 Correct 1053 ms 342268 KB Output is correct
35 Correct 1000 ms 342296 KB Output is correct
36 Correct 1014 ms 342424 KB Output is correct
37 Correct 1165 ms 342424 KB Output is correct
38 Correct 1059 ms 342972 KB Output is correct
39 Correct 1014 ms 343052 KB Output is correct
40 Correct 968 ms 343052 KB Output is correct
41 Correct 1061 ms 343052 KB Output is correct
42 Correct 917 ms 343444 KB Output is correct
43 Correct 1114 ms 343620 KB Output is correct
44 Correct 977 ms 343688 KB Output is correct
45 Correct 1068 ms 344276 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 334456 KB Output is correct
2 Correct 248 ms 334572 KB Output is correct
3 Correct 217 ms 334656 KB Output is correct
4 Correct 228 ms 334676 KB Output is correct
5 Correct 229 ms 334888 KB Output is correct
6 Correct 223 ms 334888 KB Output is correct
7 Correct 242 ms 334888 KB Output is correct
8 Correct 258 ms 334888 KB Output is correct
9 Correct 251 ms 334888 KB Output is correct
10 Correct 254 ms 334948 KB Output is correct
11 Correct 292 ms 334948 KB Output is correct
12 Correct 277 ms 334948 KB Output is correct
13 Correct 262 ms 334948 KB Output is correct
14 Correct 231 ms 334948 KB Output is correct
15 Correct 228 ms 334948 KB Output is correct
16 Correct 261 ms 334948 KB Output is correct
17 Correct 226 ms 334948 KB Output is correct
18 Correct 246 ms 334948 KB Output is correct
19 Correct 229 ms 334948 KB Output is correct
20 Correct 277 ms 334948 KB Output is correct
21 Correct 261 ms 334948 KB Output is correct
22 Correct 228 ms 334948 KB Output is correct
23 Correct 218 ms 334948 KB Output is correct
24 Correct 215 ms 334948 KB Output is correct
25 Correct 245 ms 334948 KB Output is correct
26 Correct 222 ms 335228 KB Output is correct
27 Correct 980 ms 337372 KB Output is correct
28 Correct 931 ms 337372 KB Output is correct
29 Correct 1044 ms 341516 KB Output is correct
30 Correct 948 ms 341548 KB Output is correct
31 Correct 1006 ms 341548 KB Output is correct
32 Correct 1124 ms 341548 KB Output is correct
33 Correct 1042 ms 342176 KB Output is correct
34 Correct 1053 ms 342268 KB Output is correct
35 Correct 1000 ms 342296 KB Output is correct
36 Correct 1014 ms 342424 KB Output is correct
37 Correct 1165 ms 342424 KB Output is correct
38 Correct 1059 ms 342972 KB Output is correct
39 Correct 1014 ms 343052 KB Output is correct
40 Correct 968 ms 343052 KB Output is correct
41 Correct 1061 ms 343052 KB Output is correct
42 Correct 917 ms 343444 KB Output is correct
43 Correct 1114 ms 343620 KB Output is correct
44 Correct 977 ms 343688 KB Output is correct
45 Correct 1068 ms 344276 KB Output is correct
46 Correct 396 ms 347536 KB Output is correct
47 Correct 2467 ms 414576 KB Output is correct
48 Correct 2517 ms 442676 KB Output is correct
49 Correct 2836 ms 461520 KB Output is correct
50 Correct 2671 ms 461520 KB Output is correct
51 Correct 2833 ms 461520 KB Output is correct
52 Correct 2970 ms 461564 KB Output is correct
53 Correct 2976 ms 461564 KB Output is correct
54 Correct 3075 ms 461564 KB Output is correct
55 Correct 2977 ms 461564 KB Output is correct
56 Correct 3147 ms 470896 KB Output is correct
57 Correct 3311 ms 480280 KB Output is correct
58 Correct 3119 ms 489644 KB Output is correct
59 Correct 3352 ms 499140 KB Output is correct
60 Correct 3311 ms 508168 KB Output is correct
61 Correct 3511 ms 514092 KB Output is correct
62 Correct 3236 ms 520600 KB Output is correct
63 Correct 3353 ms 523232 KB Output is correct
64 Incorrect 1881 ms 523304 KB Output isn't correct
65 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 334456 KB Output is correct
2 Correct 248 ms 334572 KB Output is correct
3 Correct 217 ms 334656 KB Output is correct
4 Correct 228 ms 334676 KB Output is correct
5 Correct 229 ms 334888 KB Output is correct
6 Correct 223 ms 334888 KB Output is correct
7 Correct 242 ms 334888 KB Output is correct
8 Correct 258 ms 334888 KB Output is correct
9 Correct 251 ms 334888 KB Output is correct
10 Correct 254 ms 334948 KB Output is correct
11 Correct 292 ms 334948 KB Output is correct
12 Correct 277 ms 334948 KB Output is correct
13 Correct 262 ms 334948 KB Output is correct
14 Correct 231 ms 334948 KB Output is correct
15 Correct 228 ms 334948 KB Output is correct
16 Correct 261 ms 334948 KB Output is correct
17 Correct 226 ms 334948 KB Output is correct
18 Correct 246 ms 334948 KB Output is correct
19 Correct 229 ms 334948 KB Output is correct
20 Correct 277 ms 334948 KB Output is correct
21 Correct 261 ms 334948 KB Output is correct
22 Correct 228 ms 334948 KB Output is correct
23 Correct 218 ms 334948 KB Output is correct
24 Correct 215 ms 334948 KB Output is correct
25 Correct 245 ms 334948 KB Output is correct
26 Correct 222 ms 335228 KB Output is correct
27 Correct 980 ms 337372 KB Output is correct
28 Correct 931 ms 337372 KB Output is correct
29 Correct 1044 ms 341516 KB Output is correct
30 Correct 948 ms 341548 KB Output is correct
31 Correct 1006 ms 341548 KB Output is correct
32 Correct 1124 ms 341548 KB Output is correct
33 Correct 1042 ms 342176 KB Output is correct
34 Correct 1053 ms 342268 KB Output is correct
35 Correct 1000 ms 342296 KB Output is correct
36 Correct 1014 ms 342424 KB Output is correct
37 Correct 1165 ms 342424 KB Output is correct
38 Correct 1059 ms 342972 KB Output is correct
39 Correct 1014 ms 343052 KB Output is correct
40 Correct 968 ms 343052 KB Output is correct
41 Correct 1061 ms 343052 KB Output is correct
42 Correct 917 ms 343444 KB Output is correct
43 Correct 1114 ms 343620 KB Output is correct
44 Correct 977 ms 343688 KB Output is correct
45 Correct 1068 ms 344276 KB Output is correct
46 Correct 396 ms 347536 KB Output is correct
47 Correct 2467 ms 414576 KB Output is correct
48 Correct 2517 ms 442676 KB Output is correct
49 Correct 2836 ms 461520 KB Output is correct
50 Correct 2671 ms 461520 KB Output is correct
51 Correct 2833 ms 461520 KB Output is correct
52 Correct 2970 ms 461564 KB Output is correct
53 Correct 2976 ms 461564 KB Output is correct
54 Correct 3075 ms 461564 KB Output is correct
55 Correct 2977 ms 461564 KB Output is correct
56 Correct 3147 ms 470896 KB Output is correct
57 Correct 3311 ms 480280 KB Output is correct
58 Correct 3119 ms 489644 KB Output is correct
59 Correct 3352 ms 499140 KB Output is correct
60 Correct 3311 ms 508168 KB Output is correct
61 Correct 3511 ms 514092 KB Output is correct
62 Correct 3236 ms 520600 KB Output is correct
63 Correct 3353 ms 523232 KB Output is correct
64 Incorrect 1881 ms 523304 KB Output isn't correct
65 Halted 0 ms 0 KB -