oj.uz

Submission #243414

# Submission time Handle Problem Language Result Execution time Memory
243414 2020-07-01T04:02:07 Z mhy908 Wild Boar (JOI18_wild_boar) C++14
100 / 100
 9516 ms 419576 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
const LL llinf=2e18;

int n, m, q, len;
int num[2010][2010], re;
vector<pii> link[2010];
LL dist[4010][4010];
bool ch[4010];

priority_queue<pair<LL, pii>, vector<pair<LL, pii> >, greater<pair<LL, pii> > > pq;
void do_dijk(int s, int e){
    memset(ch, 0, sizeof ch);
    pq.push(mp(0ll, mp(s, e)));
    dist[num[s][e]][num[s][e]]=0;
    while(!pq.empty()){
        LL d=pq.top().F;
        int fr=pq.top().S.F, nw=pq.top().S.S;
        pq.pop();
        if(ch[num[fr][nw]])continue;
        ch[num[fr][nw]]=true;
        for(auto j:link[nw]){
            if(j.F!=fr&&dist[num[s][e]][num[nw][j.F]]>d+j.S){
                dist[num[s][e]][num[nw][j.F]]=d+j.S;
                pq.push(mp(d+j.S, mp(nw, j.F)));
            }
        }
    }
}

int arr[100010];
struct NODE{
    pair<LL, pii> p[4];
    NODE(){for(int i=0; i<4; i++)p[i]=mp(llinf, mp(1, 1));}
}proc[2010][2010], tree[400010];

NODE f(NODE a, NODE b){
    NODE ret;
    vector<pair<LL, pii> > vc;
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            if(a.p[i].S.S==b.p[j].S.F)vc.eb(mp(llinf, mp(1, 1)));
            else vc.eb(mp(a.p[i].F+b.p[j].F, mp(a.p[i].S.F, b.p[j].S.S)));
        }
    }
    for(auto k:vc)ret.p[0]=min(ret.p[0], k);
    for(auto k:vc){
        if(k.S.F!=ret.p[0].S.F&&k.S.S!=ret.p[0].S.S)
            ret.p[1]=min(ret.p[1], k);
    }
    for(auto k:vc){
        if(k.S.F!=ret.p[1].S.F&&k.S.S!=ret.p[0].S.S)
            ret.p[2]=min(ret.p[2], k);
    }
    for(auto k:vc){
        if(k.S.F!=ret.p[0].S.F&&k.S.S!=ret.p[1].S.S)
            ret.p[3]=min(ret.p[3], k);
    }
    return ret;
}

void init(int point, int s, int e){
    if(s==e){
        tree[point]=proc[arr[s]][arr[s+1]];
        return;
    }
    init(point*2, s, (s+e)/2);
    init(point*2+1, (s+e)/2+1, e);
    tree[point]=f(tree[point*2], tree[point*2+1]);
}
void update(int point, int s, int e, int num){
    if(s==e){
        tree[point]=proc[arr[s]][arr[s+1]];
        return;
    }
    if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num);
    else update(point*2+1, (s+e)/2+1, e, num);
    tree[point]=f(tree[point*2], tree[point*2+1]);
}
int main(){
    scanf("%d %d %d %d", &n, &m, &q, &len);
    for(int i=1; i<=m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        link[a].eb(b, c);
        num[a][b]=++re;
        link[b].eb(a, c);
        num[b][a]=++re;
    }
    for(int i=1; i<=re; i++){
        for(int j=1; j<=re; j++)dist[i][j]=llinf;
    }
    for(int i=1; i<=n; i++){
        for(auto j:link[i])do_dijk(i, j.F);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j)continue;
            vector<pair<LL, pii> > vc;
            for(auto k1:link[i]){
                for(auto k2:link[j]){
                    vc.eb(dist[num[i][k1.F]][num[k2.F][j]]+k1.S, mp(k1.F, k2.F));
                }
            }
            for(auto k:vc)proc[i][j].p[0]=min(proc[i][j].p[0], k);
            for(auto k:vc){
                if(k.S.F!=proc[i][j].p[0].S.F&&k.S.S!=proc[i][j].p[0].S.S)
                    proc[i][j].p[1]=min(proc[i][j].p[1], k);
            }
            for(auto k:vc){
                if(k.S.F!=proc[i][j].p[1].S.F&&k.S.S!=proc[i][j].p[0].S.S)
                    proc[i][j].p[2]=min(proc[i][j].p[2], k);
            }
            for(auto k:vc){
                if(k.S.F!=proc[i][j].p[0].S.F&&k.S.S!=proc[i][j].p[1].S.S)
                    proc[i][j].p[3]=min(proc[i][j].p[3], k);
            }
        }
    }
    for(int i=1; i<=len; i++)scanf("%d", &arr[i]);
    init(1, 1, len-1);
    while(q--){
        int a, b;
        scanf("%d %d", &a, &b);
        arr[a]=b;
        if(a<len)update(1, 1, len-1, a);
        if(a>1)update(1, 1, len-1, a-1);
        printf("%lld\n", tree[1].p[0].F>=llinf?-1:tree[1].p[0].F);
    }
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:88: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, &q, &len);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:127:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=len; i++)scanf("%d", &arr[i]);
                              ~~~~~^~~~~~~~~~~~~~~
wild_boar.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 278520 KB Output is correct
2 Correct 166 ms 278560 KB Output is correct
3 Correct 153 ms 278524 KB Output is correct
4 Correct 153 ms 278520 KB Output is correct
5 Correct 162 ms 278392 KB Output is correct
6 Correct 179 ms 278520 KB Output is correct
7 Correct 160 ms 278520 KB Output is correct
8 Correct 158 ms 278520 KB Output is correct
9 Correct 160 ms 278648 KB Output is correct
10 Correct 160 ms 278520 KB Output is correct
11 Correct 159 ms 278568 KB Output is correct
12 Correct 154 ms 278524 KB Output is correct
13 Correct 172 ms 278520 KB Output is correct
14 Correct 156 ms 278520 KB Output is correct
15 Correct 155 ms 278524 KB Output is correct
16 Correct 155 ms 278648 KB Output is correct
17 Correct 164 ms 278664 KB Output is correct
18 Correct 154 ms 278520 KB Output is correct
19 Correct 178 ms 278648 KB Output is correct
20 Correct 169 ms 278648 KB Output is correct
21 Correct 171 ms 278520 KB Output is correct
22 Correct 152 ms 278520 KB Output is correct
23 Correct 155 ms 278520 KB Output is correct
24 Correct 153 ms 278520 KB Output is correct
25 Correct 173 ms 278524 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 278520 KB Output is correct
2 Correct 166 ms 278560 KB Output is correct
3 Correct 153 ms 278524 KB Output is correct
4 Correct 153 ms 278520 KB Output is correct
5 Correct 162 ms 278392 KB Output is correct
6 Correct 179 ms 278520 KB Output is correct
7 Correct 160 ms 278520 KB Output is correct
8 Correct 158 ms 278520 KB Output is correct
9 Correct 160 ms 278648 KB Output is correct
10 Correct 160 ms 278520 KB Output is correct
11 Correct 159 ms 278568 KB Output is correct
12 Correct 154 ms 278524 KB Output is correct
13 Correct 172 ms 278520 KB Output is correct
14 Correct 156 ms 278520 KB Output is correct
15 Correct 155 ms 278524 KB Output is correct
16 Correct 155 ms 278648 KB Output is correct
17 Correct 164 ms 278664 KB Output is correct
18 Correct 154 ms 278520 KB Output is correct
19 Correct 178 ms 278648 KB Output is correct
20 Correct 169 ms 278648 KB Output is correct
21 Correct 171 ms 278520 KB Output is correct
22 Correct 152 ms 278520 KB Output is correct
23 Correct 155 ms 278520 KB Output is correct
24 Correct 153 ms 278520 KB Output is correct
25 Correct 173 ms 278524 KB Output is correct
26 Correct 156 ms 278832 KB Output is correct
27 Correct 234 ms 280696 KB Output is correct
28 Correct 222 ms 280696 KB Output is correct
29 Correct 314 ms 284896 KB Output is correct
30 Correct 308 ms 284796 KB Output is correct
31 Correct 302 ms 284868 KB Output is correct
32 Correct 311 ms 284876 KB Output is correct
33 Correct 316 ms 285048 KB Output is correct
34 Correct 333 ms 285176 KB Output is correct
35 Correct 296 ms 285104 KB Output is correct
36 Correct 314 ms 285176 KB Output is correct
37 Correct 322 ms 285048 KB Output is correct
38 Correct 307 ms 285304 KB Output is correct
39 Correct 302 ms 285432 KB Output is correct
40 Correct 345 ms 285308 KB Output is correct
41 Correct 311 ms 285308 KB Output is correct
42 Correct 320 ms 285536 KB Output is correct
43 Correct 301 ms 285560 KB Output is correct
44 Correct 308 ms 285560 KB Output is correct
45 Correct 267 ms 285816 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 278520 KB Output is correct
2 Correct 166 ms 278560 KB Output is correct
3 Correct 153 ms 278524 KB Output is correct
4 Correct 153 ms 278520 KB Output is correct
5 Correct 162 ms 278392 KB Output is correct
6 Correct 179 ms 278520 KB Output is correct
7 Correct 160 ms 278520 KB Output is correct
8 Correct 158 ms 278520 KB Output is correct
9 Correct 160 ms 278648 KB Output is correct
10 Correct 160 ms 278520 KB Output is correct
11 Correct 159 ms 278568 KB Output is correct
12 Correct 154 ms 278524 KB Output is correct
13 Correct 172 ms 278520 KB Output is correct
14 Correct 156 ms 278520 KB Output is correct
15 Correct 155 ms 278524 KB Output is correct
16 Correct 155 ms 278648 KB Output is correct
17 Correct 164 ms 278664 KB Output is correct
18 Correct 154 ms 278520 KB Output is correct
19 Correct 178 ms 278648 KB Output is correct
20 Correct 169 ms 278648 KB Output is correct
21 Correct 171 ms 278520 KB Output is correct
22 Correct 152 ms 278520 KB Output is correct
23 Correct 155 ms 278520 KB Output is correct
24 Correct 153 ms 278520 KB Output is correct
25 Correct 173 ms 278524 KB Output is correct
26 Correct 156 ms 278832 KB Output is correct
27 Correct 234 ms 280696 KB Output is correct
28 Correct 222 ms 280696 KB Output is correct
29 Correct 314 ms 284896 KB Output is correct
30 Correct 308 ms 284796 KB Output is correct
31 Correct 302 ms 284868 KB Output is correct
32 Correct 311 ms 284876 KB Output is correct
33 Correct 316 ms 285048 KB Output is correct
34 Correct 333 ms 285176 KB Output is correct
35 Correct 296 ms 285104 KB Output is correct
36 Correct 314 ms 285176 KB Output is correct
37 Correct 322 ms 285048 KB Output is correct
38 Correct 307 ms 285304 KB Output is correct
39 Correct 302 ms 285432 KB Output is correct
40 Correct 345 ms 285308 KB Output is correct
41 Correct 311 ms 285308 KB Output is correct
42 Correct 320 ms 285536 KB Output is correct
43 Correct 301 ms 285560 KB Output is correct
44 Correct 308 ms 285560 KB Output is correct
45 Correct 267 ms 285816 KB Output is correct
46 Correct 370 ms 291192 KB Output is correct
47 Correct 6620 ms 410304 KB Output is correct
48 Correct 6125 ms 412436 KB Output is correct
49 Correct 5275 ms 412204 KB Output is correct
50 Correct 5639 ms 413664 KB Output is correct
51 Correct 6119 ms 414300 KB Output is correct
52 Correct 4279 ms 411240 KB Output is correct
53 Correct 4309 ms 411384 KB Output is correct
54 Correct 4254 ms 411384 KB Output is correct
55 Correct 4249 ms 411132 KB Output is correct
56 Correct 4354 ms 411924 KB Output is correct
57 Correct 4347 ms 412712 KB Output is correct
58 Correct 4415 ms 413132 KB Output is correct
59 Correct 4321 ms 413816 KB Output is correct
60 Correct 4246 ms 414456 KB Output is correct
61 Correct 4181 ms 415020 KB Output is correct
62 Correct 4056 ms 415236 KB Output is correct
63 Correct 3898 ms 415740 KB Output is correct
64 Correct 1829 ms 416504 KB Output is correct
65 Correct 1843 ms 416760 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 278520 KB Output is correct
2 Correct 166 ms 278560 KB Output is correct
3 Correct 153 ms 278524 KB Output is correct
4 Correct 153 ms 278520 KB Output is correct
5 Correct 162 ms 278392 KB Output is correct
6 Correct 179 ms 278520 KB Output is correct
7 Correct 160 ms 278520 KB Output is correct
8 Correct 158 ms 278520 KB Output is correct
9 Correct 160 ms 278648 KB Output is correct
10 Correct 160 ms 278520 KB Output is correct
11 Correct 159 ms 278568 KB Output is correct
12 Correct 154 ms 278524 KB Output is correct
13 Correct 172 ms 278520 KB Output is correct
14 Correct 156 ms 278520 KB Output is correct
15 Correct 155 ms 278524 KB Output is correct
16 Correct 155 ms 278648 KB Output is correct
17 Correct 164 ms 278664 KB Output is correct
18 Correct 154 ms 278520 KB Output is correct
19 Correct 178 ms 278648 KB Output is correct
20 Correct 169 ms 278648 KB Output is correct
21 Correct 171 ms 278520 KB Output is correct
22 Correct 152 ms 278520 KB Output is correct
23 Correct 155 ms 278520 KB Output is correct
24 Correct 153 ms 278520 KB Output is correct
25 Correct 173 ms 278524 KB Output is correct
26 Correct 156 ms 278832 KB Output is correct
27 Correct 234 ms 280696 KB Output is correct
28 Correct 222 ms 280696 KB Output is correct
29 Correct 314 ms 284896 KB Output is correct
30 Correct 308 ms 284796 KB Output is correct
31 Correct 302 ms 284868 KB Output is correct
32 Correct 311 ms 284876 KB Output is correct
33 Correct 316 ms 285048 KB Output is correct
34 Correct 333 ms 285176 KB Output is correct
35 Correct 296 ms 285104 KB Output is correct
36 Correct 314 ms 285176 KB Output is correct
37 Correct 322 ms 285048 KB Output is correct
38 Correct 307 ms 285304 KB Output is correct
39 Correct 302 ms 285432 KB Output is correct
40 Correct 345 ms 285308 KB Output is correct
41 Correct 311 ms 285308 KB Output is correct
42 Correct 320 ms 285536 KB Output is correct
43 Correct 301 ms 285560 KB Output is correct
44 Correct 308 ms 285560 KB Output is correct
45 Correct 267 ms 285816 KB Output is correct
46 Correct 370 ms 291192 KB Output is correct
47 Correct 6620 ms 410304 KB Output is correct
48 Correct 6125 ms 412436 KB Output is correct
49 Correct 5275 ms 412204 KB Output is correct
50 Correct 5639 ms 413664 KB Output is correct
51 Correct 6119 ms 414300 KB Output is correct
52 Correct 4279 ms 411240 KB Output is correct
53 Correct 4309 ms 411384 KB Output is correct
54 Correct 4254 ms 411384 KB Output is correct
55 Correct 4249 ms 411132 KB Output is correct
56 Correct 4354 ms 411924 KB Output is correct
57 Correct 4347 ms 412712 KB Output is correct
58 Correct 4415 ms 413132 KB Output is correct
59 Correct 4321 ms 413816 KB Output is correct
60 Correct 4246 ms 414456 KB Output is correct
61 Correct 4181 ms 415020 KB Output is correct
62 Correct 4056 ms 415236 KB Output is correct
63 Correct 3898 ms 415740 KB Output is correct
64 Correct 1829 ms 416504 KB Output is correct
65 Correct 1843 ms 416760 KB Output is correct
66 Correct 243 ms 279544 KB Output is correct
67 Correct 1244 ms 323836 KB Output is correct
68 Correct 1687 ms 415036 KB Output is correct
69 Correct 2496 ms 416248 KB Output is correct
70 Correct 3627 ms 417292 KB Output is correct
71 Correct 8724 ms 410508 KB Output is correct
72 Correct 8243 ms 412580 KB Output is correct
73 Correct 6426 ms 414020 KB Output is correct
74 Correct 6447 ms 413920 KB Output is correct
75 Correct 6435 ms 413816 KB Output is correct
76 Correct 7799 ms 413484 KB Output is correct
77 Correct 8204 ms 414356 KB Output is correct
78 Correct 9516 ms 418524 KB Output is correct
79 Correct 6762 ms 415284 KB Output is correct
80 Correct 6764 ms 416016 KB Output is correct
81 Correct 7208 ms 416380 KB Output is correct
82 Correct 6556 ms 417028 KB Output is correct
83 Correct 6592 ms 417060 KB Output is correct
84 Correct 6024 ms 418680 KB Output is correct
85 Correct 4211 ms 419576 KB Output is correct