Submission #46804

#	Time	Username	Problem	Language	Result	Execution time	Memory
46804		zscoder	Wild Boar (JOI18_wild_boar)	C++17	47 / 100	18066 ms	217720 KiB

wild_boar

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

vector<vi> edges;
ll dist[6111][6111];
int n,m,q,L; 
vector<pair<ii,int> > adj[2111];
vi belong[6111];
int getid(int a, int b)
{
	return (a*2+b);
}
const ll INF=ll(1e18);
int a[211111];
ll dp[2][6111];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>q>>L;
	for(int i=0;i<m;i++)
	{
		int u,v,w; cin>>u>>v>>w; u--; v--; edges.pb({u,v});
		adj[u].pb(mp(mp(v,w),i)); adj[v].pb(mp(mp(u,w),i));
	}
	int orim = m;
	for(int i=0;i<n;i++)
	{
		adj[n].pb(mp(mp(i,0),m++)); edges.pb({n,i});
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<2;j++)
		{
			belong[edges[i][j]].pb(getid(i,j));
			priority_queue<ii,vector<ii>,greater<ii> > pq;
			int s = getid(i,j);
			pq.push(mp(0,s));
			for(int k=0;k<m*2;k++) dist[s][k] = INF;
			dist[s][s] = 0;
			while(!pq.empty())
			{
				ll d=pq.top().fi; int u = pq.top().se; pq.pop();
				//cerr<<"DIST : "<<s<<' '<<u<<' '<<d<<'\n';
				int vertex = edges[u/2][u%2]; int edgeno = u/2;
				for(auto k:adj[vertex])
				{
					int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
					if(id==edgeno) continue;
					int vid = id*2;
					if(edges[id][0]!=v) vid++;
					if(dist[s][vid]>d+w)
					{
						dist[s][vid] = d + w;
						pq.push(mp(dist[s][vid], vid));
					}
				}
			}
		}
	}
	for(int i=0;i<L;i++)
	{
		cin>>a[i]; a[i]--;
	}
	for(int zz=0;zz<q;zz++)
	{
		int y,z; cin>>y>>z; y--; z--; a[y]=z;
		for(int i=0;i<m*2;i++)
		{
			dp[0][i] = INF;
		}
		/*
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<2;j++)
			{
				if(edges[i][j]==a[0])
				{
					dp[0][getid(i,j)] = 0;
				}
			}
		}
		*/
		dp[0][getid(orim + a[0],1)] = 0;
		for(int i=0;i+1<L;i++)
		{
			int pre = i&1; int cur = pre^1;
			for(int j=0;j<m*2;j++)
			{
				dp[cur][j] = INF;
			}
			for(int j=0;j<m*2;j++)
			{
				if(dp[pre][j]<INF)
				{
					ll v=dp[pre][j];
					for(int k:belong[a[i+1]])
					{
						if(dist[j][k]<INF)
						{
							dp[cur][k] = min(dp[cur][k], v + dist[j][k]);
						}
					}
				}
			}
		}
		ll mn = INF;
		for(int i=0;i<m*2;i++)
		{
			mn = min(mn, dp[(L+1)&1][i]);
		}
		if(mn>=INF) mn=-1;
		cout<<mn<<'\n';
	}
}

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