Submission #243420

#	Time	Username	Problem	Language	Result	Execution time	Memory
243420		mhy908	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	9252 ms	418508 KiB

wild_boar

#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(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[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 (stderr)

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 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38