제출 #1308734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308734		Tymond	Wild Boar (JOI18_wild_boar)	C++20	47 / 100	2496 ms	477504 KiB

wild_boar

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const ll INF = 1e16;
struct Node{
    vector<pair<ll, pll>> vec;
    Node(){
        vec = {};
    }
};

const int MAXN = 2e3 + 7;
const int MAXQ = 1e5 + 7;
int A[MAXQ];
vll g[MAXN];
pair<pll, ll> edges[MAXN];
vector<pair<ll, pll>> paths[MAXN][MAXN];
Node tree[4 * MAXQ + 7];
int n, m, q, L;

bool addPath(pair<ll, pii> x, vector<pair<ll, pll>>& p){
    if(sz(p) == 5){
        return false;
    }

    int cnt0 = 0;
    int cnt1 = 0;
    for(auto ele : p){
        if(ele.se.fi == x.se.fi && ele.se.se == x.se.se){
            return false;
        }

        if(ele.se.fi == x.se.fi){
            cnt0++;
            if(cnt0 == 2){
                return false;
            }
        }

        if(ele.se.se == x.se.se){
            cnt1++;
            if(cnt1 == 2){
                return false;
            }
        }
    }

    p.pb(x);
    return true;
}

void Dijkstra(int s){
    priority_queue<pair<ll, pair<ll, pll>>> pq;
    for(auto u : g[s]){
        pq.push(mp(-edges[u].se, mp(edges[u].fi.fi + edges[u].fi.se - s, mp(u, u))));
    }

    while(sz(pq)){
        pair<ll, pair<ll, pll>> curr = pq.top();
        pq.pop();
        curr.fi = -curr.fi;
        if(addPath(mp(curr.fi, curr.se.se), paths[s][curr.se.fi])){
            for(auto e : g[curr.se.fi]){
                if(e != curr.se.se.se){
                    pq.push(mp(-(curr.fi + edges[e].se), mp(edges[e].fi.fi + edges[e].fi.se - curr.se.fi, mp(curr.se.se.fi, e))));
                }
            }
        }
    }
}

Node merge(Node x, Node y){
    vector<pair<ll, pll>> curr = {};
    for(auto ele : x.vec){
        if(ele.fi == INF){
            continue;
        }
        for(auto ele2 : y.vec){
            if(ele2.fi == INF){
                continue;
            }
            if(ele.se.se != ele2.se.fi){
                curr.pb(mp(ele.fi + ele2.fi, mp(ele.se.fi, ele2.se.se)));
            }
        }
    }

    sort(all(curr));
    Node res;
    for(auto ele : curr){
        addPath(ele, res.vec);
    }
    return res;
}

void upd(int v, int l, int p, int ind){
    if(l > p){
        return;
    }
    if(l == p){
        tree[v].vec = paths[A[l]][A[l + 1]];
        return;
    }

    int mid = (l + p) / 2;
    if(ind <= mid){
        upd(2 * v, l, mid, ind);
    }else{
        upd(2 * v + 1, mid + 1, p, ind);
    }
    tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}

ll getAns(){
    if(L == 1){
        return 0LL;
    }
    ll mn = INF;
    for(auto ele : tree[1].vec){
        mn = min(mn, ele.fi);
    }

    if(mn == INF){
        return -1LL;
    }
    return mn;
}

void init(int v, int l, int p){
    if(l > p){
        return;
    }
    //cerr << v << ' ' << l << ' ' << p << '\n';
    if(l == p){
        //cerr << A[l] << ' ' << A[l + 1] << '\n';
        tree[v].vec = paths[A[l]][A[l + 1]];
        return;
    }

    int mid = (l + p) / 2;
    init(2 * v, l, mid);
    init(2 * v + 1, mid + 1, p);
    tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> q >> L;
    for(int i = 1; i <= m; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].pb(i);
        g[b].pb(i);
        edges[i] = mp(mp(a, b), c);
    }

    for(int i = 1; i <= n; i++){
        Dijkstra(i);
        // for(int j = 1; j <= n; j++){
        //     cerr << "======\n";
        //     cerr << i << ' ' << j << '\n';
        //     debug(paths[i][j]);
        // }
    }

    for(int i = 0; i < L; i++){
        cin >> A[i];
    }

    init(1, 0, L - 2);

    while(q--){
        int ind, x;
        cin >> ind >> x;
        ind--;
        A[ind] = x;
        if(ind - 1 >= 0){
            upd(1, 0, L - 2, ind - 1);
        }

        if(ind + 1 < L){
            upd(1, 0, L - 2, ind);
        }

        cout << getAns() << '\n';
    }

    return 0;
}

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