제출 #537156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537156		leaked	Wild Boar (JOI18_wild_boar)	C++14	47 / 100	5468 ms	1048576 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);
#define ar array
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);};
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);};
const ll inf=1e18;
const int N=1e5+1;
ar<ll,3> emp={inf,inf,inf};
struct T{
    ar<ll,3> paths[5];
    ///cost,start,end
    void init(const vec<ar<ll,3>> &goes){
        fill(paths,paths+5,emp);
        for(auto &z : goes) umin(paths[0],z);
        for(auto &z : goes){
            if(z[1]!=paths[0][1])
                umin(paths[1],z);
            if(z[2]!=paths[0][2])
                umin(paths[2],z);
        }
        for(auto &z : goes){
            if(z[1]!=paths[0][1] && z[2]!=paths[1][2])
                umin(paths[3],z);
            if(z[2]!=paths[0][2] && z[1]!=paths[2][1])
                umin(paths[4],z);
        }
    }
};
vec<ar<ll,3>> goes;
T dst[2001][2001];
vec<ar<ll,3>> jo[2001][2001];
ll dt[4001][4001];
T t[4*N];
int a[N];
vec<ar<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][2]!=t[v<<1|1].paths[j][1] && t[v<<1].paths[i][0]!=inf && t[v<<1|1].paths[j][0]!=inf)
                goes.pb({t[v<<1].paths[i][0]+t[v<<1|1].paths[j][0],t[v<<1].paths[i][1],t[v<<1|1].paths[j][2]});
        }
    }
    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<ar<ll,3>> e;
    priority_queue<ar<ll,2>,vec<ar<ll,2>>,greater<ar<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(umin(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].pb({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][0]==inf?-1:t[1].paths[0][0])<<'\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: 0 / 15
• Subtask 4: 0 / 38