oj.uz

Submission #1112263

# Submission time Handle Problem Language Result Execution time Memory
1112263 2024-11-14T00:39:04 Z azberjibiou Wild Boar (JOI18_wild_boar) C++17
47 / 100
 122 ms 116404 KB 
#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[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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 1 ms 2640 KB Output is correct
10 Correct 1 ms 760 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Correct 2 ms 10832 KB Output is correct
20 Correct 2 ms 10832 KB Output is correct
21 Correct 2 ms 8764 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8780 KB Output is correct
24 Correct 2 ms 8960 KB Output is correct
25 Correct 2 ms 8784 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 1 ms 2640 KB Output is correct
10 Correct 1 ms 760 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Correct 2 ms 10832 KB Output is correct
20 Correct 2 ms 10832 KB Output is correct
21 Correct 2 ms 8764 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8780 KB Output is correct
24 Correct 2 ms 8960 KB Output is correct
25 Correct 2 ms 8784 KB Output is correct
26 Correct 3 ms 14928 KB Output is correct
27 Correct 29 ms 68944 KB Output is correct
28 Correct 22 ms 68944 KB Output is correct
29 Correct 112 ms 81488 KB Output is correct
30 Correct 98 ms 81416 KB Output is correct
31 Correct 101 ms 81220 KB Output is correct
32 Correct 100 ms 81224 KB Output is correct
33 Correct 101 ms 93512 KB Output is correct
34 Correct 122 ms 93768 KB Output is correct
35 Correct 97 ms 93504 KB Output is correct
36 Correct 95 ms 93512 KB Output is correct
37 Correct 95 ms 93512 KB Output is correct
38 Correct 97 ms 105800 KB Output is correct
39 Correct 84 ms 105800 KB Output is correct
40 Correct 99 ms 105800 KB Output is correct
41 Correct 102 ms 105800 KB Output is correct
42 Correct 89 ms 111952 KB Output is correct
43 Correct 96 ms 114504 KB Output is correct
44 Correct 97 ms 112752 KB Output is correct
45 Correct 61 ms 116404 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 1 ms 2640 KB Output is correct
10 Correct 1 ms 760 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Correct 2 ms 10832 KB Output is correct
20 Correct 2 ms 10832 KB Output is correct
21 Correct 2 ms 8764 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8780 KB Output is correct
24 Correct 2 ms 8960 KB Output is correct
25 Correct 2 ms 8784 KB Output is correct
26 Correct 3 ms 14928 KB Output is correct
27 Correct 29 ms 68944 KB Output is correct
28 Correct 22 ms 68944 KB Output is correct
29 Correct 112 ms 81488 KB Output is correct
30 Correct 98 ms 81416 KB Output is correct
31 Correct 101 ms 81220 KB Output is correct
32 Correct 100 ms 81224 KB Output is correct
33 Correct 101 ms 93512 KB Output is correct
34 Correct 122 ms 93768 KB Output is correct
35 Correct 97 ms 93504 KB Output is correct
36 Correct 95 ms 93512 KB Output is correct
37 Correct 95 ms 93512 KB Output is correct
38 Correct 97 ms 105800 KB Output is correct
39 Correct 84 ms 105800 KB Output is correct
40 Correct 99 ms 105800 KB Output is correct
41 Correct 102 ms 105800 KB Output is correct
42 Correct 89 ms 111952 KB Output is correct
43 Correct 96 ms 114504 KB Output is correct
44 Correct 97 ms 112752 KB Output is correct
45 Correct 61 ms 116404 KB Output is correct
46 Runtime error 35 ms 2640 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 2 ms 8784 KB Output is correct
7 Correct 2 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 1 ms 2640 KB Output is correct
10 Correct 1 ms 760 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 592 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 2 ms 8784 KB Output is correct
19 Correct 2 ms 10832 KB Output is correct
20 Correct 2 ms 10832 KB Output is correct
21 Correct 2 ms 8764 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8780 KB Output is correct
24 Correct 2 ms 8960 KB Output is correct
25 Correct 2 ms 8784 KB Output is correct
26 Correct 3 ms 14928 KB Output is correct
27 Correct 29 ms 68944 KB Output is correct
28 Correct 22 ms 68944 KB Output is correct
29 Correct 112 ms 81488 KB Output is correct
30 Correct 98 ms 81416 KB Output is correct
31 Correct 101 ms 81220 KB Output is correct
32 Correct 100 ms 81224 KB Output is correct
33 Correct 101 ms 93512 KB Output is correct
34 Correct 122 ms 93768 KB Output is correct
35 Correct 97 ms 93504 KB Output is correct
36 Correct 95 ms 93512 KB Output is correct
37 Correct 95 ms 93512 KB Output is correct
38 Correct 97 ms 105800 KB Output is correct
39 Correct 84 ms 105800 KB Output is correct
40 Correct 99 ms 105800 KB Output is correct
41 Correct 102 ms 105800 KB Output is correct
42 Correct 89 ms 111952 KB Output is correct
43 Correct 96 ms 114504 KB Output is correct
44 Correct 97 ms 112752 KB Output is correct
45 Correct 61 ms 116404 KB Output is correct
46 Runtime error 35 ms 2640 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -