답안 #58214 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58214	2018-07-17T07:58:00 Z	King Suryal(#1687)	Wild Boar (JOI18_wild_boar)	C++11	100 / 100	4532 ms	546116 KB

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

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.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	334456 KB	Output is correct
2	Correct	255 ms	334664 KB	Output is correct
3	Correct	253 ms	334664 KB	Output is correct
4	Correct	290 ms	334676 KB	Output is correct
5	Correct	266 ms	334676 KB	Output is correct
6	Correct	283 ms	334888 KB	Output is correct
7	Correct	222 ms	334888 KB	Output is correct
8	Correct	273 ms	334888 KB	Output is correct
9	Correct	234 ms	334888 KB	Output is correct
10	Correct	247 ms	334888 KB	Output is correct
11	Correct	262 ms	334888 KB	Output is correct
12	Correct	228 ms	334888 KB	Output is correct
13	Correct	221 ms	334888 KB	Output is correct
14	Correct	261 ms	334888 KB	Output is correct
15	Correct	237 ms	334888 KB	Output is correct
16	Correct	264 ms	334888 KB	Output is correct
17	Correct	272 ms	334888 KB	Output is correct
18	Correct	263 ms	334888 KB	Output is correct
19	Correct	223 ms	334888 KB	Output is correct
20	Correct	234 ms	334888 KB	Output is correct
21	Correct	232 ms	334888 KB	Output is correct
22	Correct	242 ms	334888 KB	Output is correct
23	Correct	228 ms	334888 KB	Output is correct
24	Correct	246 ms	334888 KB	Output is correct
25	Correct	221 ms	334888 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	334456 KB	Output is correct
2	Correct	255 ms	334664 KB	Output is correct
3	Correct	253 ms	334664 KB	Output is correct
4	Correct	290 ms	334676 KB	Output is correct
5	Correct	266 ms	334676 KB	Output is correct
6	Correct	283 ms	334888 KB	Output is correct
7	Correct	222 ms	334888 KB	Output is correct
8	Correct	273 ms	334888 KB	Output is correct
9	Correct	234 ms	334888 KB	Output is correct
10	Correct	247 ms	334888 KB	Output is correct
11	Correct	262 ms	334888 KB	Output is correct
12	Correct	228 ms	334888 KB	Output is correct
13	Correct	221 ms	334888 KB	Output is correct
14	Correct	261 ms	334888 KB	Output is correct
15	Correct	237 ms	334888 KB	Output is correct
16	Correct	264 ms	334888 KB	Output is correct
17	Correct	272 ms	334888 KB	Output is correct
18	Correct	263 ms	334888 KB	Output is correct
19	Correct	223 ms	334888 KB	Output is correct
20	Correct	234 ms	334888 KB	Output is correct
21	Correct	232 ms	334888 KB	Output is correct
22	Correct	242 ms	334888 KB	Output is correct
23	Correct	228 ms	334888 KB	Output is correct
24	Correct	246 ms	334888 KB	Output is correct
25	Correct	221 ms	334888 KB	Output is correct
26	Correct	230 ms	335340 KB	Output is correct
27	Correct	316 ms	337132 KB	Output is correct
28	Correct	309 ms	337288 KB	Output is correct
29	Correct	359 ms	341372 KB	Output is correct
30	Correct	373 ms	341376 KB	Output is correct
31	Correct	390 ms	341376 KB	Output is correct
32	Correct	339 ms	341376 KB	Output is correct
33	Correct	405 ms	342012 KB	Output is correct
34	Correct	342 ms	342148 KB	Output is correct
35	Correct	297 ms	342148 KB	Output is correct
36	Correct	304 ms	342148 KB	Output is correct
37	Correct	349 ms	342148 KB	Output is correct
38	Correct	396 ms	342652 KB	Output is correct
39	Correct	373 ms	342796 KB	Output is correct
40	Correct	418 ms	342796 KB	Output is correct
41	Correct	366 ms	342796 KB	Output is correct
42	Correct	307 ms	343164 KB	Output is correct
43	Correct	377 ms	343632 KB	Output is correct
44	Correct	359 ms	343632 KB	Output is correct
45	Correct	349 ms	344136 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	334456 KB	Output is correct
2	Correct	255 ms	334664 KB	Output is correct
3	Correct	253 ms	334664 KB	Output is correct
4	Correct	290 ms	334676 KB	Output is correct
5	Correct	266 ms	334676 KB	Output is correct
6	Correct	283 ms	334888 KB	Output is correct
7	Correct	222 ms	334888 KB	Output is correct
8	Correct	273 ms	334888 KB	Output is correct
9	Correct	234 ms	334888 KB	Output is correct
10	Correct	247 ms	334888 KB	Output is correct
11	Correct	262 ms	334888 KB	Output is correct
12	Correct	228 ms	334888 KB	Output is correct
13	Correct	221 ms	334888 KB	Output is correct
14	Correct	261 ms	334888 KB	Output is correct
15	Correct	237 ms	334888 KB	Output is correct
16	Correct	264 ms	334888 KB	Output is correct
17	Correct	272 ms	334888 KB	Output is correct
18	Correct	263 ms	334888 KB	Output is correct
19	Correct	223 ms	334888 KB	Output is correct
20	Correct	234 ms	334888 KB	Output is correct
21	Correct	232 ms	334888 KB	Output is correct
22	Correct	242 ms	334888 KB	Output is correct
23	Correct	228 ms	334888 KB	Output is correct
24	Correct	246 ms	334888 KB	Output is correct
25	Correct	221 ms	334888 KB	Output is correct
26	Correct	230 ms	335340 KB	Output is correct
27	Correct	316 ms	337132 KB	Output is correct
28	Correct	309 ms	337288 KB	Output is correct
29	Correct	359 ms	341372 KB	Output is correct
30	Correct	373 ms	341376 KB	Output is correct
31	Correct	390 ms	341376 KB	Output is correct
32	Correct	339 ms	341376 KB	Output is correct
33	Correct	405 ms	342012 KB	Output is correct
34	Correct	342 ms	342148 KB	Output is correct
35	Correct	297 ms	342148 KB	Output is correct
36	Correct	304 ms	342148 KB	Output is correct
37	Correct	349 ms	342148 KB	Output is correct
38	Correct	396 ms	342652 KB	Output is correct
39	Correct	373 ms	342796 KB	Output is correct
40	Correct	418 ms	342796 KB	Output is correct
41	Correct	366 ms	342796 KB	Output is correct
42	Correct	307 ms	343164 KB	Output is correct
43	Correct	377 ms	343632 KB	Output is correct
44	Correct	359 ms	343632 KB	Output is correct
45	Correct	349 ms	344136 KB	Output is correct
46	Correct	347 ms	347424 KB	Output is correct
47	Correct	1574 ms	414300 KB	Output is correct
48	Correct	1943 ms	442656 KB	Output is correct
49	Correct	2048 ms	461280 KB	Output is correct
50	Correct	1935 ms	461280 KB	Output is correct
51	Correct	2192 ms	461280 KB	Output is correct
52	Correct	2234 ms	461280 KB	Output is correct
53	Correct	2559 ms	461296 KB	Output is correct
54	Correct	2352 ms	461360 KB	Output is correct
55	Correct	2214 ms	461360 KB	Output is correct
56	Correct	2382 ms	470668 KB	Output is correct
57	Correct	2475 ms	480012 KB	Output is correct
58	Correct	2495 ms	489528 KB	Output is correct
59	Correct	2585 ms	498812 KB	Output is correct
60	Correct	2534 ms	507812 KB	Output is correct
61	Correct	2790 ms	514024 KB	Output is correct
62	Correct	2773 ms	520172 KB	Output is correct
63	Correct	2944 ms	523064 KB	Output is correct
64	Correct	1454 ms	523064 KB	Output is correct
65	Correct	1317 ms	523756 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	334456 KB	Output is correct
2	Correct	255 ms	334664 KB	Output is correct
3	Correct	253 ms	334664 KB	Output is correct
4	Correct	290 ms	334676 KB	Output is correct
5	Correct	266 ms	334676 KB	Output is correct
6	Correct	283 ms	334888 KB	Output is correct
7	Correct	222 ms	334888 KB	Output is correct
8	Correct	273 ms	334888 KB	Output is correct
9	Correct	234 ms	334888 KB	Output is correct
10	Correct	247 ms	334888 KB	Output is correct
11	Correct	262 ms	334888 KB	Output is correct
12	Correct	228 ms	334888 KB	Output is correct
13	Correct	221 ms	334888 KB	Output is correct
14	Correct	261 ms	334888 KB	Output is correct
15	Correct	237 ms	334888 KB	Output is correct
16	Correct	264 ms	334888 KB	Output is correct
17	Correct	272 ms	334888 KB	Output is correct
18	Correct	263 ms	334888 KB	Output is correct
19	Correct	223 ms	334888 KB	Output is correct
20	Correct	234 ms	334888 KB	Output is correct
21	Correct	232 ms	334888 KB	Output is correct
22	Correct	242 ms	334888 KB	Output is correct
23	Correct	228 ms	334888 KB	Output is correct
24	Correct	246 ms	334888 KB	Output is correct
25	Correct	221 ms	334888 KB	Output is correct
26	Correct	230 ms	335340 KB	Output is correct
27	Correct	316 ms	337132 KB	Output is correct
28	Correct	309 ms	337288 KB	Output is correct
29	Correct	359 ms	341372 KB	Output is correct
30	Correct	373 ms	341376 KB	Output is correct
31	Correct	390 ms	341376 KB	Output is correct
32	Correct	339 ms	341376 KB	Output is correct
33	Correct	405 ms	342012 KB	Output is correct
34	Correct	342 ms	342148 KB	Output is correct
35	Correct	297 ms	342148 KB	Output is correct
36	Correct	304 ms	342148 KB	Output is correct
37	Correct	349 ms	342148 KB	Output is correct
38	Correct	396 ms	342652 KB	Output is correct
39	Correct	373 ms	342796 KB	Output is correct
40	Correct	418 ms	342796 KB	Output is correct
41	Correct	366 ms	342796 KB	Output is correct
42	Correct	307 ms	343164 KB	Output is correct
43	Correct	377 ms	343632 KB	Output is correct
44	Correct	359 ms	343632 KB	Output is correct
45	Correct	349 ms	344136 KB	Output is correct
46	Correct	347 ms	347424 KB	Output is correct
47	Correct	1574 ms	414300 KB	Output is correct
48	Correct	1943 ms	442656 KB	Output is correct
49	Correct	2048 ms	461280 KB	Output is correct
50	Correct	1935 ms	461280 KB	Output is correct
51	Correct	2192 ms	461280 KB	Output is correct
52	Correct	2234 ms	461280 KB	Output is correct
53	Correct	2559 ms	461296 KB	Output is correct
54	Correct	2352 ms	461360 KB	Output is correct
55	Correct	2214 ms	461360 KB	Output is correct
56	Correct	2382 ms	470668 KB	Output is correct
57	Correct	2475 ms	480012 KB	Output is correct
58	Correct	2495 ms	489528 KB	Output is correct
59	Correct	2585 ms	498812 KB	Output is correct
60	Correct	2534 ms	507812 KB	Output is correct
61	Correct	2790 ms	514024 KB	Output is correct
62	Correct	2773 ms	520172 KB	Output is correct
63	Correct	2944 ms	523064 KB	Output is correct
64	Correct	1454 ms	523064 KB	Output is correct
65	Correct	1317 ms	523756 KB	Output is correct
66	Correct	340 ms	523756 KB	Output is correct
67	Correct	1012 ms	523756 KB	Output is correct
68	Correct	1252 ms	523792 KB	Output is correct
69	Correct	1885 ms	524836 KB	Output is correct
70	Correct	2835 ms	526728 KB	Output is correct
71	Correct	3492 ms	526728 KB	Output is correct
72	Correct	3654 ms	526728 KB	Output is correct
73	Correct	4482 ms	526728 KB	Output is correct
74	Correct	4182 ms	526728 KB	Output is correct
75	Correct	4032 ms	526728 KB	Output is correct
76	Correct	4091 ms	526728 KB	Output is correct
77	Correct	3788 ms	526728 KB	Output is correct
78	Correct	3465 ms	526728 KB	Output is correct
79	Correct	4374 ms	526728 KB	Output is correct
80	Correct	4151 ms	526728 KB	Output is correct
81	Correct	3908 ms	526728 KB	Output is correct
82	Correct	4302 ms	526980 KB	Output is correct
83	Correct	4532 ms	534220 KB	Output is correct
84	Correct	4245 ms	544632 KB	Output is correct
85	Correct	3228 ms	546116 KB	Output is correct

답안 #58214

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 38.0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
38.0 / 38.0