Submission #1305655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305655		Zbyszek99	Wild Boar (JOI18_wild_boar)	C++20	100 / 100	3005 ms	714452 KiB

wild_boar

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const ll INF = 1e18+50;
const ll MOD = 1e9+7;

struct path
{
    int a,b;
    ll d;
    bool operator<(const path& other) const
    {
        return d < other.d;
    }
};


vector<path> connection[2001][2001];
vector<pii> graph[2001];
ll cost[2005];
ll dist[2005];
int n,m,q,L;

const int tree_pot = 17;
const int tree_siz = (1<<(tree_pot+1))-1;
int arr[(1<<(tree_pot))+2];

struct node
{
    int l,r;
    ll ans[5][5];
    node()
    {
        rep(i,5)
        {
            rep(j,5) ans[i][j] = INF;
        }
    }
    node operator+(const node& other)
    {
        node res;
        res.l = l;
        res.r = other.r;
        rep(i,5)
        {
            rep(j,5)
            {
                rep(k,5)
                {
                    res.ans[i][j] = min(res.ans[i][j],ans[i][k]+other.ans[k][j]+connection[arr[r]][arr[r+1]][k].d);
                }
            }
        }
        return res;
    }
};

node nodes[tree_siz+1];

void upd_node(int v)
{
    nodes[v] = nodes[v*2]+nodes[v*2+1];
}

void set_beg_matrix(int ind)
{
    int v = tree_siz/2+ind;
    rep(i,5) rep(j,5) nodes[v].ans[i][j] = INF;
    rep(i,5) rep(j,5) if(connection[arr[ind-1]][arr[ind]][i].b != connection[arr[ind]][arr[ind+1]][j].a) nodes[v].ans[i][j] = 0;
}

void upd_ind(int ind, int val)
{
    arr[ind] = val;
    int v = tree_siz/2+ind;
    vi nums = {v};
    vi nums2 = {};
    if(ind != 1) nums.pb(v-1);
    if(v != tree_siz) nums.pb(v+1);
    forall(it,nums) set_beg_matrix(it-tree_siz/2);
    while(nums[0] != 1)
    {
        forall(it,nums) 
        {
            bool was = 0;
            forall(it2,nums2) if(it2 == it/2) was = 1;
            if(!was) nums2.pb(it/2);
        }
        swap(nums,nums2);
        nums2 = {};
        forall(it,nums) upd_node(it);
    }
}

bool add_path(vector<path>& p, path a)
{
    if(a.d < p[0].d)
    {
        p[0] = a;
        return 1;
    }
    if(a.a != p[0].a && a.d < p[1].d)
    {
        p[1] = a;
        return 1;
    }
    if(a.a != p[0].a && a.b != p[1].b && a.d < p[2].d)
    {
        p[2] = a;
        return 1;
    }
    if(a.b != p[0].b && a.d < p[3].d)
    {
        p[3] = a;
        return 1;
    }
    if(a.b != p[0].b && a.a != p[3].a && a.d < p[4].d)
    {
        p[4] = a;
        return 1;
    }
    return 0;
}

void calc_paths(int a)
{
    priority_queue<pair<path,int>,vector<pair<path,int>>,greater<pair<path,int>>> pq;
    forall(it,graph[a]) pq.push({{it.ss,it.ss,cost[it.ss]},it.ff});
    while(!pq.empty())
    {
        pair<path,int> elm = pq.top();
        pq.pop();
        if(!add_path(connection[a][elm.ss],elm.ff)) continue;
        forall(it,graph[elm.ss])
        {
            if(it.ss != elm.ff.b) pq.push({{elm.ff.a,it.ss,elm.ff.d+cost[it.ss]},it.ff});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n >> m >> q >> L;
    rep2(i,1,m)
    {
        int a,b;
        cin >> a >> b >> cost[i];
        graph[a].pb({b,i});
        graph[b].pb({a,i});
    }
    rep2(i,0,n)
    {
        rep(k,5)
        {
            connection[0][i].pb({0,-1,0});
            connection[i][0].pb({0,-1,0});
        }
    }
    rep2(i,1,n) rep2(j,1,n) rep(k,5) connection[i][j].pb({-1,-1,INF});
    rep2(i,1,n) calc_paths(i);
    rep(i,L) cin >> arr[i+1];
    rep2(i,tree_siz/2+1,tree_siz)
    {
        nodes[i].l = i-tree_siz/2;
        nodes[i].r = i-tree_siz/2;
    }
    rep2(i,1,tree_siz/2+1) set_beg_matrix(i);
    for(int i = tree_siz/2; i >= 1; i--) upd_node(i);
    rep(qq,q)
    {
        int p,val;
        cin >> p >> val;
        upd_ind(p,val);
        ll ans = INF;
        rep(i,5) rep(j,5) ans = min(ans,nodes[1].ans[i][j]);
        if(ans != INF) cout << ans << "\n";
        else cout << "-1\n";
    }
}

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