oj.uz

Submission #537157

# Submission time Handle Problem Language Result Execution time Memory
537157 2022-03-14T16:45:53 Z leaked Wild Boar (JOI18_wild_boar) C++14
100 / 100
 6258 ms 941972 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 439372 KB Output is correct
2 Correct 219 ms 439180 KB Output is correct
3 Correct 240 ms 439100 KB Output is correct
4 Correct 222 ms 439176 KB Output is correct
5 Correct 226 ms 439124 KB Output is correct
6 Correct 237 ms 439132 KB Output is correct
7 Correct 223 ms 439232 KB Output is correct
8 Correct 248 ms 439132 KB Output is correct
9 Correct 227 ms 439200 KB Output is correct
10 Correct 225 ms 439176 KB Output is correct
11 Correct 241 ms 439188 KB Output is correct
12 Correct 216 ms 439192 KB Output is correct
13 Correct 235 ms 439256 KB Output is correct
14 Correct 251 ms 439232 KB Output is correct
15 Correct 227 ms 439168 KB Output is correct
16 Correct 236 ms 439108 KB Output is correct
17 Correct 230 ms 439212 KB Output is correct
18 Correct 230 ms 439120 KB Output is correct
19 Correct 237 ms 439220 KB Output is correct
20 Correct 225 ms 439116 KB Output is correct
21 Correct 229 ms 439264 KB Output is correct
22 Correct 245 ms 439196 KB Output is correct
23 Correct 221 ms 439216 KB Output is correct
24 Correct 260 ms 439136 KB Output is correct
25 Correct 223 ms 439124 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 439372 KB Output is correct
2 Correct 219 ms 439180 KB Output is correct
3 Correct 240 ms 439100 KB Output is correct
4 Correct 222 ms 439176 KB Output is correct
5 Correct 226 ms 439124 KB Output is correct
6 Correct 237 ms 439132 KB Output is correct
7 Correct 223 ms 439232 KB Output is correct
8 Correct 248 ms 439132 KB Output is correct
9 Correct 227 ms 439200 KB Output is correct
10 Correct 225 ms 439176 KB Output is correct
11 Correct 241 ms 439188 KB Output is correct
12 Correct 216 ms 439192 KB Output is correct
13 Correct 235 ms 439256 KB Output is correct
14 Correct 251 ms 439232 KB Output is correct
15 Correct 227 ms 439168 KB Output is correct
16 Correct 236 ms 439108 KB Output is correct
17 Correct 230 ms 439212 KB Output is correct
18 Correct 230 ms 439120 KB Output is correct
19 Correct 237 ms 439220 KB Output is correct
20 Correct 225 ms 439116 KB Output is correct
21 Correct 229 ms 439264 KB Output is correct
22 Correct 245 ms 439196 KB Output is correct
23 Correct 221 ms 439216 KB Output is correct
24 Correct 260 ms 439136 KB Output is correct
25 Correct 223 ms 439124 KB Output is correct
26 Correct 231 ms 439748 KB Output is correct
27 Correct 245 ms 441316 KB Output is correct
28 Correct 237 ms 441288 KB Output is correct
29 Correct 350 ms 453276 KB Output is correct
30 Correct 344 ms 453052 KB Output is correct
31 Correct 336 ms 452892 KB Output is correct
32 Correct 332 ms 453244 KB Output is correct
33 Correct 340 ms 453408 KB Output is correct
34 Correct 320 ms 453508 KB Output is correct
35 Correct 337 ms 453112 KB Output is correct
36 Correct 356 ms 453136 KB Output is correct
37 Correct 350 ms 453576 KB Output is correct
38 Correct 331 ms 453460 KB Output is correct
39 Correct 331 ms 452984 KB Output is correct
40 Correct 336 ms 453344 KB Output is correct
41 Correct 345 ms 453612 KB Output is correct
42 Correct 322 ms 453412 KB Output is correct
43 Correct 328 ms 453376 KB Output is correct
44 Correct 343 ms 453392 KB Output is correct
45 Correct 279 ms 449440 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 439372 KB Output is correct
2 Correct 219 ms 439180 KB Output is correct
3 Correct 240 ms 439100 KB Output is correct
4 Correct 222 ms 439176 KB Output is correct
5 Correct 226 ms 439124 KB Output is correct
6 Correct 237 ms 439132 KB Output is correct
7 Correct 223 ms 439232 KB Output is correct
8 Correct 248 ms 439132 KB Output is correct
9 Correct 227 ms 439200 KB Output is correct
10 Correct 225 ms 439176 KB Output is correct
11 Correct 241 ms 439188 KB Output is correct
12 Correct 216 ms 439192 KB Output is correct
13 Correct 235 ms 439256 KB Output is correct
14 Correct 251 ms 439232 KB Output is correct
15 Correct 227 ms 439168 KB Output is correct
16 Correct 236 ms 439108 KB Output is correct
17 Correct 230 ms 439212 KB Output is correct
18 Correct 230 ms 439120 KB Output is correct
19 Correct 237 ms 439220 KB Output is correct
20 Correct 225 ms 439116 KB Output is correct
21 Correct 229 ms 439264 KB Output is correct
22 Correct 245 ms 439196 KB Output is correct
23 Correct 221 ms 439216 KB Output is correct
24 Correct 260 ms 439136 KB Output is correct
25 Correct 223 ms 439124 KB Output is correct
26 Correct 231 ms 439748 KB Output is correct
27 Correct 245 ms 441316 KB Output is correct
28 Correct 237 ms 441288 KB Output is correct
29 Correct 350 ms 453276 KB Output is correct
30 Correct 344 ms 453052 KB Output is correct
31 Correct 336 ms 452892 KB Output is correct
32 Correct 332 ms 453244 KB Output is correct
33 Correct 340 ms 453408 KB Output is correct
34 Correct 320 ms 453508 KB Output is correct
35 Correct 337 ms 453112 KB Output is correct
36 Correct 356 ms 453136 KB Output is correct
37 Correct 350 ms 453576 KB Output is correct
38 Correct 331 ms 453460 KB Output is correct
39 Correct 331 ms 452984 KB Output is correct
40 Correct 336 ms 453344 KB Output is correct
41 Correct 345 ms 453612 KB Output is correct
42 Correct 322 ms 453412 KB Output is correct
43 Correct 328 ms 453376 KB Output is correct
44 Correct 343 ms 453392 KB Output is correct
45 Correct 279 ms 449440 KB Output is correct
46 Correct 456 ms 473824 KB Output is correct
47 Correct 5630 ms 895944 KB Output is correct
48 Correct 5170 ms 892444 KB Output is correct
49 Correct 4643 ms 917080 KB Output is correct
50 Correct 4769 ms 906188 KB Output is correct
51 Correct 5203 ms 904920 KB Output is correct
52 Correct 4075 ms 932472 KB Output is correct
53 Correct 4056 ms 935520 KB Output is correct
54 Correct 4062 ms 930624 KB Output is correct
55 Correct 4108 ms 933996 KB Output is correct
56 Correct 4177 ms 936044 KB Output is correct
57 Correct 4278 ms 935356 KB Output is correct
58 Correct 4145 ms 934788 KB Output is correct
59 Correct 4117 ms 939844 KB Output is correct
60 Correct 4187 ms 936128 KB Output is correct
61 Correct 4150 ms 935700 KB Output is correct
62 Correct 3918 ms 928108 KB Output is correct
63 Correct 3595 ms 919796 KB Output is correct
64 Correct 1567 ms 761860 KB Output is correct
65 Correct 1599 ms 762312 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 439372 KB Output is correct
2 Correct 219 ms 439180 KB Output is correct
3 Correct 240 ms 439100 KB Output is correct
4 Correct 222 ms 439176 KB Output is correct
5 Correct 226 ms 439124 KB Output is correct
6 Correct 237 ms 439132 KB Output is correct
7 Correct 223 ms 439232 KB Output is correct
8 Correct 248 ms 439132 KB Output is correct
9 Correct 227 ms 439200 KB Output is correct
10 Correct 225 ms 439176 KB Output is correct
11 Correct 241 ms 439188 KB Output is correct
12 Correct 216 ms 439192 KB Output is correct
13 Correct 235 ms 439256 KB Output is correct
14 Correct 251 ms 439232 KB Output is correct
15 Correct 227 ms 439168 KB Output is correct
16 Correct 236 ms 439108 KB Output is correct
17 Correct 230 ms 439212 KB Output is correct
18 Correct 230 ms 439120 KB Output is correct
19 Correct 237 ms 439220 KB Output is correct
20 Correct 225 ms 439116 KB Output is correct
21 Correct 229 ms 439264 KB Output is correct
22 Correct 245 ms 439196 KB Output is correct
23 Correct 221 ms 439216 KB Output is correct
24 Correct 260 ms 439136 KB Output is correct
25 Correct 223 ms 439124 KB Output is correct
26 Correct 231 ms 439748 KB Output is correct
27 Correct 245 ms 441316 KB Output is correct
28 Correct 237 ms 441288 KB Output is correct
29 Correct 350 ms 453276 KB Output is correct
30 Correct 344 ms 453052 KB Output is correct
31 Correct 336 ms 452892 KB Output is correct
32 Correct 332 ms 453244 KB Output is correct
33 Correct 340 ms 453408 KB Output is correct
34 Correct 320 ms 453508 KB Output is correct
35 Correct 337 ms 453112 KB Output is correct
36 Correct 356 ms 453136 KB Output is correct
37 Correct 350 ms 453576 KB Output is correct
38 Correct 331 ms 453460 KB Output is correct
39 Correct 331 ms 452984 KB Output is correct
40 Correct 336 ms 453344 KB Output is correct
41 Correct 345 ms 453612 KB Output is correct
42 Correct 322 ms 453412 KB Output is correct
43 Correct 328 ms 453376 KB Output is correct
44 Correct 343 ms 453392 KB Output is correct
45 Correct 279 ms 449440 KB Output is correct
46 Correct 456 ms 473824 KB Output is correct
47 Correct 5630 ms 895944 KB Output is correct
48 Correct 5170 ms 892444 KB Output is correct
49 Correct 4643 ms 917080 KB Output is correct
50 Correct 4769 ms 906188 KB Output is correct
51 Correct 5203 ms 904920 KB Output is correct
52 Correct 4075 ms 932472 KB Output is correct
53 Correct 4056 ms 935520 KB Output is correct
54 Correct 4062 ms 930624 KB Output is correct
55 Correct 4108 ms 933996 KB Output is correct
56 Correct 4177 ms 936044 KB Output is correct
57 Correct 4278 ms 935356 KB Output is correct
58 Correct 4145 ms 934788 KB Output is correct
59 Correct 4117 ms 939844 KB Output is correct
60 Correct 4187 ms 936128 KB Output is correct
61 Correct 4150 ms 935700 KB Output is correct
62 Correct 3918 ms 928108 KB Output is correct
63 Correct 3595 ms 919796 KB Output is correct
64 Correct 1567 ms 761860 KB Output is correct
65 Correct 1599 ms 762312 KB Output is correct
66 Correct 253 ms 440296 KB Output is correct
67 Correct 539 ms 512176 KB Output is correct
68 Correct 1040 ms 693232 KB Output is correct
69 Correct 1178 ms 695876 KB Output is correct
70 Correct 1337 ms 696440 KB Output is correct
71 Correct 6016 ms 891732 KB Output is correct
72 Correct 5602 ms 904004 KB Output is correct
73 Correct 4531 ms 934100 KB Output is correct
74 Correct 4640 ms 937480 KB Output is correct
75 Correct 4561 ms 935120 KB Output is correct
76 Correct 5073 ms 919004 KB Output is correct
77 Correct 5511 ms 907696 KB Output is correct
78 Correct 6258 ms 904904 KB Output is correct
79 Correct 4656 ms 940612 KB Output is correct
80 Correct 4705 ms 940068 KB Output is correct
81 Correct 5220 ms 931264 KB Output is correct
82 Correct 4499 ms 941972 KB Output is correct
83 Correct 4480 ms 941564 KB Output is correct
84 Correct 4178 ms 924468 KB Output is correct
85 Correct 2019 ms 765084 KB Output is correct