oj.uz

Submission #243204

# Submission time Handle Problem Language Result Execution time Memory
243204 2020-06-30T14:32:07 Z mhy908 Wild Boar (JOI18_wild_boar) C++14
0 / 100
 189 ms 278648 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<pii> 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){
    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[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(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[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[1].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:82: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:85: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:121: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:125: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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 278500 KB Output is correct
2 Correct 168 ms 278520 KB Output is correct
3 Correct 168 ms 278572 KB Output is correct
4 Correct 170 ms 278588 KB Output is correct
5 Correct 189 ms 278520 KB Output is correct
6 Correct 163 ms 278520 KB Output is correct
7 Correct 171 ms 278648 KB Output is correct
8 Correct 181 ms 278496 KB Output is correct
9 Correct 162 ms 278544 KB Output is correct
10 Correct 178 ms 278496 KB Output is correct
11 Correct 169 ms 278648 KB Output is correct
12 Correct 169 ms 278520 KB Output is correct
13 Correct 170 ms 278516 KB Output is correct
14 Correct 170 ms 278480 KB Output is correct
15 Incorrect 180 ms 278520 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 278500 KB Output is correct
2 Correct 168 ms 278520 KB Output is correct
3 Correct 168 ms 278572 KB Output is correct
4 Correct 170 ms 278588 KB Output is correct
5 Correct 189 ms 278520 KB Output is correct
6 Correct 163 ms 278520 KB Output is correct
7 Correct 171 ms 278648 KB Output is correct
8 Correct 181 ms 278496 KB Output is correct
9 Correct 162 ms 278544 KB Output is correct
10 Correct 178 ms 278496 KB Output is correct
11 Correct 169 ms 278648 KB Output is correct
12 Correct 169 ms 278520 KB Output is correct
13 Correct 170 ms 278516 KB Output is correct
14 Correct 170 ms 278480 KB Output is correct
15 Incorrect 180 ms 278520 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 278500 KB Output is correct
2 Correct 168 ms 278520 KB Output is correct
3 Correct 168 ms 278572 KB Output is correct
4 Correct 170 ms 278588 KB Output is correct
5 Correct 189 ms 278520 KB Output is correct
6 Correct 163 ms 278520 KB Output is correct
7 Correct 171 ms 278648 KB Output is correct
8 Correct 181 ms 278496 KB Output is correct
9 Correct 162 ms 278544 KB Output is correct
10 Correct 178 ms 278496 KB Output is correct
11 Correct 169 ms 278648 KB Output is correct
12 Correct 169 ms 278520 KB Output is correct
13 Correct 170 ms 278516 KB Output is correct
14 Correct 170 ms 278480 KB Output is correct
15 Incorrect 180 ms 278520 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 278500 KB Output is correct
2 Correct 168 ms 278520 KB Output is correct
3 Correct 168 ms 278572 KB Output is correct
4 Correct 170 ms 278588 KB Output is correct
5 Correct 189 ms 278520 KB Output is correct
6 Correct 163 ms 278520 KB Output is correct
7 Correct 171 ms 278648 KB Output is correct
8 Correct 181 ms 278496 KB Output is correct
9 Correct 162 ms 278544 KB Output is correct
10 Correct 178 ms 278496 KB Output is correct
11 Correct 169 ms 278648 KB Output is correct
12 Correct 169 ms 278520 KB Output is correct
13 Correct 170 ms 278516 KB Output is correct
14 Correct 170 ms 278480 KB Output is correct
15 Incorrect 180 ms 278520 KB Output isn't correct
16 Halted 0 ms 0 KB -