Submission #537157

#	Time	Username	Problem	Language	Result	Execution time	Memory
537157		leaked	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	6258 ms	941972 KiB

wild_boar

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
template<class T> bool chmin(T &a,const T &b){return (a>b?a=b,1:0);};
template<class T> bool chmax(T &a,const T &b){return (a<b?a=b,1:0);};
const ll inf=1e18;
const int N=1e5+1;
struct ar{
    ll a;int b,c;
    ar(){
        a=inf;b=-1;c=-1;
    }
    ar(ll _x,int x,int y):a(_x),b(x),c(y){}
    const bool operator <(const ar &o){
        return make_tuple(a,b,c)<make_tuple(o.a,o.b,o.c);
    }
};
void umin(ar &a,const ar &b){
    if(a.a>b.a)
        a=b;
}
ar emp=ar(inf,-1,-1);
struct T{
    ar paths[5];
    T(){
        fill(paths,paths+5,emp);
    }
    ///cost,start,end
    void init(vec<ar> &goes){
        fill(paths,paths+5,emp);
        for(auto &z : goes) umin(paths[0],z);
        for(auto &z : goes){
            if(z.b!=paths[0].b)
                umin(paths[1],z);
            if(z.c!=paths[0].c)
                umin(paths[2],z);
        }
        for(auto &z : goes){
            if(z.b!=paths[0].b && z.c!=paths[1].c)
                umin(paths[3],z);
            if(z.c!=paths[0].c && z.b!=paths[2].b)
                umin(paths[4],z);
        }
        goes.clear();
    }
};
vec<ar> goes;
T dst[2001][2001];
vec<ar> jo[2001][2001];
ll dt[4001][4001];
T t[4*N];
int a[N];
vec<array<ll,3>> g[2001];
void pull(int v){
    goes.clear();
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(t[v<<1].paths[i].c!=t[v<<1|1].paths[j].b && t[v<<1].paths[i].a!=inf && t[v<<1|1].paths[j].a!=inf)
                goes.emplace_back(t[v<<1].paths[i].a+t[v<<1|1].paths[j].a,t[v<<1].paths[i].b,t[v<<1|1].paths[j].c);
        }
    }
    t[v].init(goes);
}
void build(int v,int tl,int tr){
    if(tl==tr){
        t[v]=dst[a[tl-1]][a[tl]];
    }
    else{
        int tm=(tl+tr)>>1;
        build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
        pull(v);
    }
}
void upd(int i,int v,int tl,int tr){
    if(tl==tr){
        t[v]=dst[a[tl-1]][a[tl]];
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=i)
        upd(i,v<<1,tl,tm);
    else
        upd(i,v<<1|1,tm+1,tr);
    pull(v);
}
signed main(){
    fast_resp;
    int n,m,k,q;
    cin>>n>>m>>q>>k;
    vec<array<ll,3>> e;
    priority_queue<array<ll,2>,vec<array<ll,2>>,greater<array<ll,2>>>pq;
    for(int i=0;i<m;i++){
        int v,u,c;
        cin>>v>>u>>c;--v;--u;
        g[v].pb({c,u,sz(e)});
        e.pb({v,u,c});
        g[u].pb({c,v,sz(e)});
        e.pb({u,v,c});
    }
    for(int i=0;i<sz(e);i++){
        fill(dt[i],dt[i]+sz(e),inf);
        dt[i][i]=e[i][2];
        pq.push({e[i][2],i});
        while(!pq.empty()){
            auto c=pq.top();pq.pop();
            if(c[0]!=dt[i][c[1]]) continue;
            int v=e[c[1]][1];
            int last=e[c[1]][0];
            ll cst=c[0];
//            cout<<"I "<<i<<' '<<cst<<' '<<
            for(auto &u : g[v]){
                if(last==u[1]) continue;
                if(chmin(dt[i][u[2]],cst+u[0])){
                    pq.push({dt[i][u[2]],u[2]});
                }
            }
        }
    }
    for(int i=0;i<sz(e);i++){
        for(int j=0;j<sz(e);j++){
            if(dt[i][j]==inf) continue;
            int v=e[i][0],u=e[j][1];
            jo[v][u].emplace_back(dt[i][j],e[i][1],e[j][0]);
        }
    }
//    return 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            dst[i][j].init(jo[i][j]);
    }
//    return 0;
    for(int i=0;i<k;i++) cin>>a[i],--a[i];
//    return 0;
    build(1,1,k-1);
//    return 0;
    while(q--){
        int i,x;
        cin>>i>>x;--i;--x;
        a[i]=x;
        if(i+1<k) upd(i+1,1,1,k-1);
        if(i) upd(i,1,1,k-1);
        cout<<(t[1].paths[0].a==inf?-1:t[1].paths[0].a)<<'\n';
    }
    return 0;
}
/*
4 4 1 3
1 2 1
2 3 1
1 3 1
1 4 1
2
4
2
2 4
*/

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38