Submission #1112265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112265		azberjibiou	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	4983 ms	646820 KiB

wild_boar

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
typedef long long ll;
typedef array<ll, 3> p3;
typedef array<p3, 5> node;
/* 
    d[0] : 최단 경로
    d[1] : d[0]의 시작 간선이 불가능할 때 최단경로
    d[2] : d[0]의 시작 간선과 d[1]의 끝 간선이 불가능할 때 최단경로
    d[3] : d[0]의 끝 간선이 불가능할 때 최단경로
    d[4] : d[0]의 끝 간선과 d[3]의 시작 간선이 불가능할 때 최단경로
    각 경로에 대해서 (길이, 시작 간선, 끝 간선)으로 저장
    경로가 없으면 -1
*/
const int mxN=2050;
const int mxQ=100100;
const int MOD=998244353;
const ll INF=1e18; // max = 2MCL = 4e17
p3 mn(p3 a, p3 b){return a[0]<b[0] ? a : b;}
int N, M, Q, L;
node mrg(node a, node b){
    node no, res;
    for(int i=0;i<5;i++) no[i][0]=-1, res[i][0]=INF;
    if(a[0][0]==-1 || b[0][0]==-1) return no;
    array <ll, 2> cond;
    array <ll, 3> tmp;
    for(int i=0;i<5;i++){
        if(i==2 && res[1][0]==INF) continue;
        if(i==4 && res[3][0]==INF) continue;
        cond={-1, -1}, tmp={INF, 0, 0};
        // set cond
        if(i==1 || i==2) cond[0]=res[0][1];
        if(i==2) cond[1]=res[1][2];
        if(i==3 || i==4) cond[1]=res[0][2];
        if(i==4) cond[0]=res[3][1];
        // find shortest path
        for(int j=0;j<5;j++) if(a[j][0]!=-1){
            if(a[j][1]==cond[0]) continue;
            if(abs(b[0][1]-a[j][2])!=M){
                if(b[0][2]!=cond[1]) tmp={a[j][0]+b[0][0], a[j][1], b[0][2]};
                else if(b[3][0]!=-1 && abs(b[3][1]-a[j][2])!=M) tmp={a[j][0]+b[3][0], a[j][1], b[3][2]};
                else if(b[4][0]!=-1) tmp={a[j][0]+b[4][0], a[j][1], b[4][2]};
            }
            else{
                if(b[1][0]!=-1 && b[1][2]!=cond[1]) tmp={a[j][0]+b[1][0], a[j][1], b[1][2]};
                else if(b[2][0]!=-1) tmp={a[j][0]+b[2][0], a[j][1], b[2][2]};
            }
            res[i]=mn(res[i], tmp);
        }
        if(res[i][0]==INF) res[i][0]=-1;
    }
    return res;
}
p3 E[mxN];
pii eidx[mxN]; // i번째 edge가 v[a]에서 몇번째인지
vector <p3> v[mxN];
vector <pll> nv[6*mxN];
int A[mxQ];
pii qry[mxQ];
int pdeg[mxN];
ll dist[2*mxN][2*mxN];
pii se[2*mxN][2*mxN];
node D[mxN][mxN];
void input(){
    cin >> N >> M >> Q >> L;
    for(int i=0;i<M;i++){
        int a, b, c;
        cin >> a >> b >> c;
        eidx[i]=pii(v[a].size(), v[b].size());
        v[a].push_back({b, c, i});
        v[b].push_back({a, c, i});
        E[i][0]=a, E[i][1]=b, E[i][2]=c;
    }
    for(int i=1;i<=L;i++) cin >> A[i];
    for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}
void makeGraph(){
    // 0~2M-1 : edge
    // 2M-1~4M-1 : prefix of edges
    // 4M~6M-1 : suffix of edges
    for(int i=1;i<=N;i++) pdeg[i]=v[i].size();
    for(int i=2;i<=N;i++) pdeg[i]+=pdeg[i-1];
    for(int i=1;i<=N;i++){
        int sz=v[i].size();
        int st=pdeg[i-1];
        for(int j=0;j<sz;j++){
            // i에서 j번째로 나가는 간선 : s -> e, 비용 x, 간선 번호 idx
            // 역간선은 e에서 ipos번째로 나가는 간선
            int s=i;
            auto [e, x, idx] = v[i][j];
            int now = s<e ? idx : idx+M;
            int ipos = (s<e ? eidx[idx].se : eidx[idx].fi);

            // real edge에서 나가는 간선
            if(ipos!=0) nv[now].emplace_back(2*M+pdeg[e-1]+ipos-1, 0);
            if(ipos!=v[e].size()-1) nv[now].emplace_back(4*M+pdeg[e-1]+ipos+1, 0);

            // prefix 만들기
            // 2M+st+j -> 2M+st+j-1
            // 2M+st+j -> v[i][j]
            if(j!=0) nv[2*M+st+j].emplace_back(2*M+st+j-1, 0);
            nv[2*M+st+j].emplace_back(now, x);

            // suffix 만들기
            // 4M+st+j -> 4M+st+j+1
            // 4M+st+j -> v[i][j]
            if(j!=sz-1) nv[4*M+st+j].emplace_back(4*M+st+j+1, 0);
            nv[4*M+st+j].emplace_back(now, x);
        }
    }
    /*
    for(int i=0;i<6*M;i++){
        printf("%d: ", i);
        for(auto [nxt, x] : nv[i]) printf("(%lld %lld) ", nxt, x);
        printf("\n");
    }
    */
}
ll d[6*mxN];
void dijk(int st){
    for(int i=0;i<6*M;i++) d[i]=INF;
    ll pred=0;
    priority_queue <pll> pq;
    queue <int> que;
    que.push(st);
    while(pq.size() || que.size()){
        int now;
        ll x;
        if(que.size()){
            now=que.front();
            x=pred;
            que.pop();
        }
        else{
            now=pq.top().se;
            x=-pq.top().fi;
            pq.pop();
        }
        if(d[now]!=INF) continue;
        d[now]=x;
        pred=x;
        for(auto [nxt, val] : nv[now]){
            if(val==0) que.push(nxt);
            else pq.emplace(-x-val, nxt);
        }
    }
    for(int i=0;i<2*M;i++) dist[st][i]=d[i];

}
void solvDist(){
    for(int i=0;i<2*M;i++){
        dijk(i);
    }
    /*
    for(int i=0;i<2*M;i++){
        for(int j=0;j<2*M;j++){
            printf("dist[%d][%d]=%lld\n", i, j, dist[i][j]);
        }
    }
    */
}
void print(node a){
    for(int i=0;i<5;i++){
        printf("%d: ", i);
        for(int j=0;j<3;j++){
            printf("%lld ", a[i][j]);
        }
        printf("\n");
    }
}
void makeD(){
    for(int z=0;z<5;z++){
        for(int i=1;i<=N;i++) for(int j=1;j<=N;j++){
            if(i==j) continue;
            D[i][j][z][0]=INF;
            for(auto [e1, x1, idx1] : v[i]) for(auto [s2, x2, idx2] : v[j]){
                int s1=i, e2=j;
                int i1=(s1<e1 ? idx1 : idx1+M), i2=(s2<e2 ? idx2 : idx2+M);
                bool ok=true;
                if(1<=z && z<=2 && D[i][j][0][1]==i1) ok=false;
                if(z==2 && D[i][j][1][2]==i2) ok=false;
                if(3<=z && z<=4 && D[i][j][0][2]==i2) ok=false;
                if(z==4 && D[i][j][3][1]==i1) ok=false;
                if(ok) D[i][j][z]=mn(D[i][j][z], p3{dist[i1][i2]+E[idx1][2], i1, i2});
                //if(ok) printf("i=%d, j=%d, i1=%d, i2=%d\n", i, j, i1, i2);
                //if(ok) printf("D[%d][%d][%d][0]=%lld\n", i, j, z, D[i][j][z][0]);
            }
            if(D[i][j][z][0]==INF) D[i][j][z][0]=-1;
        }
    }
    /*
    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++){
        printf("%d %d: \n", i, j);
        print(D[i][j]);
    }
    */
}
node seg[4*mxQ];
void init(int idx, int s, int e){
    if(s==e){
        seg[idx]=D[A[s]][A[s+1]];
        //printf("s=%d, e=%d\n", s, e);
        //print(seg[idx]);
        return;
    }
    int mid=(s+e)/2;
    init(2*idx, s, mid);
    init(2*idx+1, mid+1, e);
    seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
    //printf("s=%d, e=%d\n", s, e);
    //print(seg[idx]);
}
void upd(int idx, int s, int e, int pos){
    if(s==e){
        seg[idx]=D[A[s]][A[s+1]];
        return;
    }
    int mid=(s+e)/2;
    if(pos<=mid) upd(2*idx, s, mid, pos);
    else upd(2*idx+1, mid+1, e, pos);
    seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
}
void sweep(){
    init(1, 1, L-1);
    for(int i=1;i<=Q;i++){
        A[qry[i].fi]=qry[i].se;
        if(qry[i].fi!=L) upd(1, 1, L-1, qry[i].fi);
        if(qry[i].fi!=1) upd(1, 1, L-1, qry[i].fi-1);
        cout << seg[1][0][0] << '\n';
    }
}
int main(){
    gibon
    input();
    makeGraph();
    solvDist();
    makeD();
    sweep();
}

Compilation message (stderr)

wild_boar.cpp: In function 'void makeGraph()':
wild_boar.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             if(ipos!=v[e].size()-1) nv[now].emplace_back(4*M+pdeg[e-1]+ipos+1, 0);
      |                ~~~~^~~~~~~~~~~~~~~

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