Submission #524462

#	Time	Username	Problem	Language	Result	Execution time	Memory
524462		alirezasamimi100	Wild Boar (JOI18_wild_boar)	C++17	47 / 100	9587 ms	1764 KiB

wild_boar

/*#pragma GCC optimize("Ofast,unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
using point=complex<double>;
#define F first
#define S second
//#define X real()
//#define Y imag()
#define pb push_back
#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define kill(x) cout << x << '\n';exit(0)
#define killshayan kill("done!")
#define killmashtali kill("Hello, World!")
const int N=2e3+10,LN=19,M=1e5+10,SQ=450,BS=737,inf=1e9,NSQ=N/SQ+1;
const ll INF=1e16;
const double pi=acos(-1);
const ld ep=1e-7;
const int MH=1000696969,MD=998244353,MOD=1000000007;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pii, null_type,greater<pii>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
int n,m,q,k,w[N],x[M];
ll dp[2][N],ans;
int ed[N];
vector<int> adj[N];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
int main(){
    fast_io;
    cin >> n >> m >> q >> k;
    if(q>1) return 0;
    for(int i=1; i<=m; i++){
        int v,u;
        cin >> v >> u >> w[i];
        ed[i*2]=u;
        ed[i*2+1]=v;
        adj[v].pb(i*2);
        adj[u].pb(i*2+1);
    }
    for(int i=1; i<=k; i++) cin >> x[i];
    int P,Q;
    cin >> P >> Q;
    x[P]=Q;
    ed[1]=x[1];
    for(ll i=0; i<m*2+2; i++) dp[0][i]=dp[1][i]=INF;
    dp[0][1]=0;
    for(int t=1; t<k; t++){
        for(int i=1; i<m*2+2; i++){
            if(dp[0][i]<INF){
                pq.push({dp[0][i],i});
            }
        }
        while(!pq.empty()){
            int id=pq.top().S;
            ll c=pq.top().F;
            pq.pop();
            if(dp[0][id]!=c) continue;
            int v=ed[id];
            for(ll i : adj[v]){
                if((i^1)==id) continue;
                int u=ed[i],f=w[i/2];
                if(dp[0][i]>f+c){
                    dp[0][i]=f+c;
                    pq.push({dp[0][i],i});
                }
                if(u==x[t+1] && dp[1][i]>f+c) dp[1][i]=f+c;
            }
        }
        for(int i=1; i<m*2+2; i++){
            dp[0][i]=dp[1][i];
            dp[1][i]=INF;
        }
    }
    ans=INF;
    for(int i=1; i<m*2+2; i++) if(dp[0][i]<ans) ans=dp[0][i];
    if(ans>=INF) ans=-1;
    cout << ans << '\n';
    return 0;
}

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