oj.uz

Submission #243171

# Submission time Handle Problem Language Result Execution time Memory
243171 2020-06-30T13:38:44 Z mhy908 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 1954 ms 1039480 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=2000000000000000;

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

priority_queue<pair<LL, pii>, vector<pair<LL, pii> >, greater<pair<LL, pii> > > pq;
void do_dijk(int s, int e){
    for(int i=1; i<=re; i++){
        pq.push(mp(0ll, mp(s, e)));
        while(!pq.empty()){
            LL d=pq.top().F;
            int fr=pq.top().S.F, nw=pq.top().S.S;
            pq.pop();
            if(d>=dist[num[s][e]][num[fr][nw]])continue;
            dist[num[s][e]][num[fr][nw]]=d;
            for(auto j:link[nw]){
                if(j.F!=fr)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(0, 0));}
}proc[4010][4010], 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(0, 0)));
            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[e+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[e+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, (LL)c);
        num[a][b]=++re;
        link[b].eb(a, (LL)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:84: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:87: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:123: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:127: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 595 ms 1032536 KB Output is correct
2 Correct 548 ms 1032520 KB Output is correct
3 Correct 543 ms 1032440 KB Output is correct
4 Correct 580 ms 1032468 KB Output is correct
5 Correct 581 ms 1032604 KB Output is correct
6 Correct 571 ms 1032440 KB Output is correct
7 Correct 564 ms 1032628 KB Output is correct
8 Correct 595 ms 1032568 KB Output is correct
9 Correct 570 ms 1032652 KB Output is correct
10 Correct 548 ms 1032568 KB Output is correct
11 Correct 603 ms 1032696 KB Output is correct
12 Correct 549 ms 1032696 KB Output is correct
13 Correct 597 ms 1032696 KB Output is correct
14 Correct 602 ms 1032696 KB Output is correct
15 Correct 568 ms 1032568 KB Output is correct
16 Correct 556 ms 1032568 KB Output is correct
17 Correct 571 ms 1032568 KB Output is correct
18 Correct 554 ms 1032568 KB Output is correct
19 Correct 603 ms 1032568 KB Output is correct
20 Correct 574 ms 1032568 KB Output is correct
21 Correct 571 ms 1032568 KB Output is correct
22 Correct 585 ms 1032568 KB Output is correct
23 Correct 586 ms 1032568 KB Output is correct
24 Correct 605 ms 1032568 KB Output is correct
25 Correct 595 ms 1032496 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 1032536 KB Output is correct
2 Correct 548 ms 1032520 KB Output is correct
3 Correct 543 ms 1032440 KB Output is correct
4 Correct 580 ms 1032468 KB Output is correct
5 Correct 581 ms 1032604 KB Output is correct
6 Correct 571 ms 1032440 KB Output is correct
7 Correct 564 ms 1032628 KB Output is correct
8 Correct 595 ms 1032568 KB Output is correct
9 Correct 570 ms 1032652 KB Output is correct
10 Correct 548 ms 1032568 KB Output is correct
11 Correct 603 ms 1032696 KB Output is correct
12 Correct 549 ms 1032696 KB Output is correct
13 Correct 597 ms 1032696 KB Output is correct
14 Correct 602 ms 1032696 KB Output is correct
15 Correct 568 ms 1032568 KB Output is correct
16 Correct 556 ms 1032568 KB Output is correct
17 Correct 571 ms 1032568 KB Output is correct
18 Correct 554 ms 1032568 KB Output is correct
19 Correct 603 ms 1032568 KB Output is correct
20 Correct 574 ms 1032568 KB Output is correct
21 Correct 571 ms 1032568 KB Output is correct
22 Correct 585 ms 1032568 KB Output is correct
23 Correct 586 ms 1032568 KB Output is correct
24 Correct 605 ms 1032568 KB Output is correct
25 Correct 595 ms 1032496 KB Output is correct
26 Correct 597 ms 1032984 KB Output is correct
27 Correct 661 ms 1034488 KB Output is correct
28 Correct 685 ms 1034616 KB Output is correct
29 Correct 911 ms 1038840 KB Output is correct
30 Correct 1182 ms 1038828 KB Output is correct
31 Correct 1954 ms 1039128 KB Output is correct
32 Correct 1926 ms 1038888 KB Output is correct
33 Correct 840 ms 1039096 KB Output is correct
34 Correct 804 ms 1038868 KB Output is correct
35 Correct 1656 ms 1039032 KB Output is correct
36 Correct 1356 ms 1039224 KB Output is correct
37 Correct 833 ms 1039008 KB Output is correct
38 Correct 801 ms 1039224 KB Output is correct
39 Correct 985 ms 1039224 KB Output is correct
40 Correct 768 ms 1039224 KB Output is correct
41 Correct 810 ms 1039096 KB Output is correct
42 Correct 873 ms 1039280 KB Output is correct
43 Correct 772 ms 1039224 KB Output is correct
44 Correct 765 ms 1039352 KB Output is correct
45 Incorrect 647 ms 1039480 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 1032536 KB Output is correct
2 Correct 548 ms 1032520 KB Output is correct
3 Correct 543 ms 1032440 KB Output is correct
4 Correct 580 ms 1032468 KB Output is correct
5 Correct 581 ms 1032604 KB Output is correct
6 Correct 571 ms 1032440 KB Output is correct
7 Correct 564 ms 1032628 KB Output is correct
8 Correct 595 ms 1032568 KB Output is correct
9 Correct 570 ms 1032652 KB Output is correct
10 Correct 548 ms 1032568 KB Output is correct
11 Correct 603 ms 1032696 KB Output is correct
12 Correct 549 ms 1032696 KB Output is correct
13 Correct 597 ms 1032696 KB Output is correct
14 Correct 602 ms 1032696 KB Output is correct
15 Correct 568 ms 1032568 KB Output is correct
16 Correct 556 ms 1032568 KB Output is correct
17 Correct 571 ms 1032568 KB Output is correct
18 Correct 554 ms 1032568 KB Output is correct
19 Correct 603 ms 1032568 KB Output is correct
20 Correct 574 ms 1032568 KB Output is correct
21 Correct 571 ms 1032568 KB Output is correct
22 Correct 585 ms 1032568 KB Output is correct
23 Correct 586 ms 1032568 KB Output is correct
24 Correct 605 ms 1032568 KB Output is correct
25 Correct 595 ms 1032496 KB Output is correct
26 Correct 597 ms 1032984 KB Output is correct
27 Correct 661 ms 1034488 KB Output is correct
28 Correct 685 ms 1034616 KB Output is correct
29 Correct 911 ms 1038840 KB Output is correct
30 Correct 1182 ms 1038828 KB Output is correct
31 Correct 1954 ms 1039128 KB Output is correct
32 Correct 1926 ms 1038888 KB Output is correct
33 Correct 840 ms 1039096 KB Output is correct
34 Correct 804 ms 1038868 KB Output is correct
35 Correct 1656 ms 1039032 KB Output is correct
36 Correct 1356 ms 1039224 KB Output is correct
37 Correct 833 ms 1039008 KB Output is correct
38 Correct 801 ms 1039224 KB Output is correct
39 Correct 985 ms 1039224 KB Output is correct
40 Correct 768 ms 1039224 KB Output is correct
41 Correct 810 ms 1039096 KB Output is correct
42 Correct 873 ms 1039280 KB Output is correct
43 Correct 772 ms 1039224 KB Output is correct
44 Correct 765 ms 1039352 KB Output is correct
45 Incorrect 647 ms 1039480 KB Output isn't correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 1032536 KB Output is correct
2 Correct 548 ms 1032520 KB Output is correct
3 Correct 543 ms 1032440 KB Output is correct
4 Correct 580 ms 1032468 KB Output is correct
5 Correct 581 ms 1032604 KB Output is correct
6 Correct 571 ms 1032440 KB Output is correct
7 Correct 564 ms 1032628 KB Output is correct
8 Correct 595 ms 1032568 KB Output is correct
9 Correct 570 ms 1032652 KB Output is correct
10 Correct 548 ms 1032568 KB Output is correct
11 Correct 603 ms 1032696 KB Output is correct
12 Correct 549 ms 1032696 KB Output is correct
13 Correct 597 ms 1032696 KB Output is correct
14 Correct 602 ms 1032696 KB Output is correct
15 Correct 568 ms 1032568 KB Output is correct
16 Correct 556 ms 1032568 KB Output is correct
17 Correct 571 ms 1032568 KB Output is correct
18 Correct 554 ms 1032568 KB Output is correct
19 Correct 603 ms 1032568 KB Output is correct
20 Correct 574 ms 1032568 KB Output is correct
21 Correct 571 ms 1032568 KB Output is correct
22 Correct 585 ms 1032568 KB Output is correct
23 Correct 586 ms 1032568 KB Output is correct
24 Correct 605 ms 1032568 KB Output is correct
25 Correct 595 ms 1032496 KB Output is correct
26 Correct 597 ms 1032984 KB Output is correct
27 Correct 661 ms 1034488 KB Output is correct
28 Correct 685 ms 1034616 KB Output is correct
29 Correct 911 ms 1038840 KB Output is correct
30 Correct 1182 ms 1038828 KB Output is correct
31 Correct 1954 ms 1039128 KB Output is correct
32 Correct 1926 ms 1038888 KB Output is correct
33 Correct 840 ms 1039096 KB Output is correct
34 Correct 804 ms 1038868 KB Output is correct
35 Correct 1656 ms 1039032 KB Output is correct
36 Correct 1356 ms 1039224 KB Output is correct
37 Correct 833 ms 1039008 KB Output is correct
38 Correct 801 ms 1039224 KB Output is correct
39 Correct 985 ms 1039224 KB Output is correct
40 Correct 768 ms 1039224 KB Output is correct
41 Correct 810 ms 1039096 KB Output is correct
42 Correct 873 ms 1039280 KB Output is correct
43 Correct 772 ms 1039224 KB Output is correct
44 Correct 765 ms 1039352 KB Output is correct
45 Incorrect 647 ms 1039480 KB Output isn't correct