Submission #1305479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305479		Zbyszek99	Wild Boar (JOI18_wild_boar)	C++20	47 / 100	18091 ms	62720 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;
    }
};


path connection[2001][2001][5];
vector<pii> graph[2001];
ll cost[2005];
ll dist[2005];
bool is_bad[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);
    }
}

void dijkstra(int beg, vi& bad, pll add = {-1,-1})
{
    forall(it,bad) is_bad[it] = 1;
    rep2(i,1,n) dist[i] = INF;
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,beg});
    if(add.ff != -1) pq.push(add);
    while(!pq.empty())
    {
        pll t = pq.top();
        pq.pop();
        if(dist[t.ss] != INF) continue;
        dist[t.ss] = t.ff;
        forall(it,graph[t.ss])
        {
            if(!is_bad[it.ss]) pq.push({t.ff+cost[it.ss],it.ff});
        }
    }
    forall(it,bad) is_bad[it] = 0;
}

int pop[2001];

ll find_cycle(int beg, vi& bad)
{
    forall(it,bad) is_bad[it] = 1;
    rep2(i,1,n) dist[i] = INF;
    priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>> pq;
    pq.push({0,{beg,-1}});
    while(!pq.empty())
    {
        pair<ll,pii> t = pq.top();
        pq.pop();
        if(dist[t.ss.ff] != INF) continue;
        dist[t.ss.ff] = t.ff;
        pop[t.ss.ff] = t.ss.ss; 
        forall(it,graph[t.ss.ff])
        {
            if(!is_bad[it.ss]) pq.push({t.ff+cost[it.ss],{it.ff,it.ss}});
        }
    }
    forall(it,bad) is_bad[it] = 0;
    ll ans = INF;
    rep2(i,1,n)
    {
        forall(it,graph[i])
        {
            if(pop[i] != it.ss && pop[it.ff] != it.ss) ans = min(ans,dist[i]+dist[it.ff]+cost[it.ss]);
        }
    }
    return ans;
}

void calc_connection(int a, int b)
{
    vector<path> paths;
    vi bad;
    forall(it,graph[b]) bad.pb(it.ss);
    forall(it,graph[a])
    {
        if(it.ff == b) paths.pb({it.ss,it.ss,cost[it.ss]});
        bad.pb(it.ss);
        ll cycle = find_cycle(it.ff,bad);
        dijkstra(it.ff,bad,{cycle+cost[it.ss],a});
        forall(it2,graph[b])
        {
            paths.pb({it.ss,it2.ss,dist[it2.ff]+cost[it.ss]+cost[it2.ss]});
        }
        bad.pop_back();
    }
    sort(all(paths));
    int p1 = paths[0].a;
    int p2 = paths[0].b;
    vector<path> rel = {paths[0]};
    bool was = 0;
    forall(it,paths)
    {
        if(it.a != p1)
        {
            rel.pb(it);
            was = 1;
            break;
        }
    }
    if(was)
    {
        forall(it,paths)
        {
            if(it.a != p1 && it.b != rel.back().b)
            {
                rel.pb(it);
                was = 1;
                break;
            }
        }
    }
    was = 0;
    forall(it,paths)
    {
        if(it.b != p2)
        {
            rel.pb(it);
            was = 1;
            break;
        }
    }
    if(was)
    {
        forall(it,paths)
        {
            if(it.b != p2 && it.a != rel.back().a)
            {
                rel.pb(it);
                was = 1;
                break;
            }
        }
    }
    while(siz(rel) < 5) rel.pb(rel[0]);
    rep(i,5) connection[a][b][i] = rel[i];
}

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][k] = {0,-1,0};
            connection[i][0][k] = {0,-1,0};
        }
    }
    rep2(i,1,n) rep2(j,1,n) if(i != j) calc_connection(i,j);
    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) upd_ind(i,arr[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: 0 / 15
• Subtask 4: 0 / 38