oj.uz

Submission #58211

# Submission time Handle Problem Language Result Execution time Memory
58211 2018-07-17T07:35:30 Z King Suryal(#1687) Wild Boar (JOI18_wild_boar) C++11
47 / 100
 3711 ms 535236 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 &p) const {
        return c > p.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] = 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 465 ms 334388 KB Output is correct
2 Correct 272 ms 334764 KB Output is correct
3 Correct 262 ms 334764 KB Output is correct
4 Correct 256 ms 334764 KB Output is correct
5 Correct 256 ms 334764 KB Output is correct
6 Correct 260 ms 334848 KB Output is correct
7 Correct 245 ms 334848 KB Output is correct
8 Correct 248 ms 334848 KB Output is correct
9 Correct 255 ms 334856 KB Output is correct
10 Correct 273 ms 334856 KB Output is correct
11 Correct 285 ms 334856 KB Output is correct
12 Correct 225 ms 334856 KB Output is correct
13 Correct 229 ms 334856 KB Output is correct
14 Correct 231 ms 334856 KB Output is correct
15 Correct 266 ms 334928 KB Output is correct
16 Correct 258 ms 334928 KB Output is correct
17 Correct 255 ms 334928 KB Output is correct
18 Correct 243 ms 334928 KB Output is correct
19 Correct 233 ms 334928 KB Output is correct
20 Correct 238 ms 334928 KB Output is correct
21 Correct 233 ms 334928 KB Output is correct
22 Correct 236 ms 334928 KB Output is correct
23 Correct 241 ms 334928 KB Output is correct
24 Correct 270 ms 334928 KB Output is correct
25 Correct 246 ms 334928 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 334388 KB Output is correct
2 Correct 272 ms 334764 KB Output is correct
3 Correct 262 ms 334764 KB Output is correct
4 Correct 256 ms 334764 KB Output is correct
5 Correct 256 ms 334764 KB Output is correct
6 Correct 260 ms 334848 KB Output is correct
7 Correct 245 ms 334848 KB Output is correct
8 Correct 248 ms 334848 KB Output is correct
9 Correct 255 ms 334856 KB Output is correct
10 Correct 273 ms 334856 KB Output is correct
11 Correct 285 ms 334856 KB Output is correct
12 Correct 225 ms 334856 KB Output is correct
13 Correct 229 ms 334856 KB Output is correct
14 Correct 231 ms 334856 KB Output is correct
15 Correct 266 ms 334928 KB Output is correct
16 Correct 258 ms 334928 KB Output is correct
17 Correct 255 ms 334928 KB Output is correct
18 Correct 243 ms 334928 KB Output is correct
19 Correct 233 ms 334928 KB Output is correct
20 Correct 238 ms 334928 KB Output is correct
21 Correct 233 ms 334928 KB Output is correct
22 Correct 236 ms 334928 KB Output is correct
23 Correct 241 ms 334928 KB Output is correct
24 Correct 270 ms 334928 KB Output is correct
25 Correct 246 ms 334928 KB Output is correct
26 Correct 263 ms 335208 KB Output is correct
27 Correct 941 ms 337432 KB Output is correct
28 Correct 1104 ms 337808 KB Output is correct
29 Correct 1117 ms 342328 KB Output is correct
30 Correct 1150 ms 342368 KB Output is correct
31 Correct 1097 ms 342660 KB Output is correct
32 Correct 1145 ms 342748 KB Output is correct
33 Correct 1094 ms 343900 KB Output is correct
34 Correct 1016 ms 344188 KB Output is correct
35 Correct 1006 ms 344500 KB Output is correct
36 Correct 1046 ms 344500 KB Output is correct
37 Correct 1051 ms 345060 KB Output is correct
38 Correct 1151 ms 345952 KB Output is correct
39 Correct 1118 ms 346232 KB Output is correct
40 Correct 1164 ms 346480 KB Output is correct
41 Correct 1144 ms 346808 KB Output is correct
42 Correct 1041 ms 347664 KB Output is correct
43 Correct 1244 ms 348100 KB Output is correct
44 Correct 1157 ms 348620 KB Output is correct
45 Correct 1283 ms 349448 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 334388 KB Output is correct
2 Correct 272 ms 334764 KB Output is correct
3 Correct 262 ms 334764 KB Output is correct
4 Correct 256 ms 334764 KB Output is correct
5 Correct 256 ms 334764 KB Output is correct
6 Correct 260 ms 334848 KB Output is correct
7 Correct 245 ms 334848 KB Output is correct
8 Correct 248 ms 334848 KB Output is correct
9 Correct 255 ms 334856 KB Output is correct
10 Correct 273 ms 334856 KB Output is correct
11 Correct 285 ms 334856 KB Output is correct
12 Correct 225 ms 334856 KB Output is correct
13 Correct 229 ms 334856 KB Output is correct
14 Correct 231 ms 334856 KB Output is correct
15 Correct 266 ms 334928 KB Output is correct
16 Correct 258 ms 334928 KB Output is correct
17 Correct 255 ms 334928 KB Output is correct
18 Correct 243 ms 334928 KB Output is correct
19 Correct 233 ms 334928 KB Output is correct
20 Correct 238 ms 334928 KB Output is correct
21 Correct 233 ms 334928 KB Output is correct
22 Correct 236 ms 334928 KB Output is correct
23 Correct 241 ms 334928 KB Output is correct
24 Correct 270 ms 334928 KB Output is correct
25 Correct 246 ms 334928 KB Output is correct
26 Correct 263 ms 335208 KB Output is correct
27 Correct 941 ms 337432 KB Output is correct
28 Correct 1104 ms 337808 KB Output is correct
29 Correct 1117 ms 342328 KB Output is correct
30 Correct 1150 ms 342368 KB Output is correct
31 Correct 1097 ms 342660 KB Output is correct
32 Correct 1145 ms 342748 KB Output is correct
33 Correct 1094 ms 343900 KB Output is correct
34 Correct 1016 ms 344188 KB Output is correct
35 Correct 1006 ms 344500 KB Output is correct
36 Correct 1046 ms 344500 KB Output is correct
37 Correct 1051 ms 345060 KB Output is correct
38 Correct 1151 ms 345952 KB Output is correct
39 Correct 1118 ms 346232 KB Output is correct
40 Correct 1164 ms 346480 KB Output is correct
41 Correct 1144 ms 346808 KB Output is correct
42 Correct 1041 ms 347664 KB Output is correct
43 Correct 1244 ms 348100 KB Output is correct
44 Correct 1157 ms 348620 KB Output is correct
45 Correct 1283 ms 349448 KB Output is correct
46 Correct 377 ms 352800 KB Output is correct
47 Correct 2427 ms 419916 KB Output is correct
48 Correct 2751 ms 448548 KB Output is correct
49 Correct 2829 ms 466904 KB Output is correct
50 Correct 2806 ms 467024 KB Output is correct
51 Correct 2726 ms 467308 KB Output is correct
52 Correct 3044 ms 467640 KB Output is correct
53 Correct 3076 ms 468040 KB Output is correct
54 Correct 3130 ms 468548 KB Output is correct
55 Correct 3219 ms 468964 KB Output is correct
56 Correct 3066 ms 478736 KB Output is correct
57 Correct 3280 ms 489196 KB Output is correct
58 Correct 3196 ms 498696 KB Output is correct
59 Correct 3353 ms 508260 KB Output is correct
60 Correct 3611 ms 517696 KB Output is correct
61 Correct 3479 ms 524996 KB Output is correct
62 Correct 3710 ms 531468 KB Output is correct
63 Correct 3711 ms 534956 KB Output is correct
64 Incorrect 1933 ms 535236 KB Output isn't correct
65 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 334388 KB Output is correct
2 Correct 272 ms 334764 KB Output is correct
3 Correct 262 ms 334764 KB Output is correct
4 Correct 256 ms 334764 KB Output is correct
5 Correct 256 ms 334764 KB Output is correct
6 Correct 260 ms 334848 KB Output is correct
7 Correct 245 ms 334848 KB Output is correct
8 Correct 248 ms 334848 KB Output is correct
9 Correct 255 ms 334856 KB Output is correct
10 Correct 273 ms 334856 KB Output is correct
11 Correct 285 ms 334856 KB Output is correct
12 Correct 225 ms 334856 KB Output is correct
13 Correct 229 ms 334856 KB Output is correct
14 Correct 231 ms 334856 KB Output is correct
15 Correct 266 ms 334928 KB Output is correct
16 Correct 258 ms 334928 KB Output is correct
17 Correct 255 ms 334928 KB Output is correct
18 Correct 243 ms 334928 KB Output is correct
19 Correct 233 ms 334928 KB Output is correct
20 Correct 238 ms 334928 KB Output is correct
21 Correct 233 ms 334928 KB Output is correct
22 Correct 236 ms 334928 KB Output is correct
23 Correct 241 ms 334928 KB Output is correct
24 Correct 270 ms 334928 KB Output is correct
25 Correct 246 ms 334928 KB Output is correct
26 Correct 263 ms 335208 KB Output is correct
27 Correct 941 ms 337432 KB Output is correct
28 Correct 1104 ms 337808 KB Output is correct
29 Correct 1117 ms 342328 KB Output is correct
30 Correct 1150 ms 342368 KB Output is correct
31 Correct 1097 ms 342660 KB Output is correct
32 Correct 1145 ms 342748 KB Output is correct
33 Correct 1094 ms 343900 KB Output is correct
34 Correct 1016 ms 344188 KB Output is correct
35 Correct 1006 ms 344500 KB Output is correct
36 Correct 1046 ms 344500 KB Output is correct
37 Correct 1051 ms 345060 KB Output is correct
38 Correct 1151 ms 345952 KB Output is correct
39 Correct 1118 ms 346232 KB Output is correct
40 Correct 1164 ms 346480 KB Output is correct
41 Correct 1144 ms 346808 KB Output is correct
42 Correct 1041 ms 347664 KB Output is correct
43 Correct 1244 ms 348100 KB Output is correct
44 Correct 1157 ms 348620 KB Output is correct
45 Correct 1283 ms 349448 KB Output is correct
46 Correct 377 ms 352800 KB Output is correct
47 Correct 2427 ms 419916 KB Output is correct
48 Correct 2751 ms 448548 KB Output is correct
49 Correct 2829 ms 466904 KB Output is correct
50 Correct 2806 ms 467024 KB Output is correct
51 Correct 2726 ms 467308 KB Output is correct
52 Correct 3044 ms 467640 KB Output is correct
53 Correct 3076 ms 468040 KB Output is correct
54 Correct 3130 ms 468548 KB Output is correct
55 Correct 3219 ms 468964 KB Output is correct
56 Correct 3066 ms 478736 KB Output is correct
57 Correct 3280 ms 489196 KB Output is correct
58 Correct 3196 ms 498696 KB Output is correct
59 Correct 3353 ms 508260 KB Output is correct
60 Correct 3611 ms 517696 KB Output is correct
61 Correct 3479 ms 524996 KB Output is correct
62 Correct 3710 ms 531468 KB Output is correct
63 Correct 3711 ms 534956 KB Output is correct
64 Incorrect 1933 ms 535236 KB Output isn't correct
65 Halted 0 ms 0 KB -