Submission #47631

#	Time	Username	Problem	Language	Result	Execution time	Memory
47631		zscoder	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	9209 ms	810792 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<pair<int,int> > edges;
ll dist[4111][4111];
int n,m,q,L; 
vector<pair<ii,int> > adj[2111];
vi in[2111];
vi out[2111];
ll orid[2001][2001];
int getid(int a, int b)
{
	return (a*2+b);
}
const ll INF=ll(1e18);
int a[211111];
ll D[2111][2111][5];
vector<pair<int,int> > paths[2111][2111];
vector<ll> W;
 
const int DIM = 5;
struct state
{
	ll a[DIM][DIM];
	ll *operator [] (int r) { return a[r]; };
	state(ll x = 0)
	{
		memset(a, 0, sizeof a);
		if(x)
		{
			for(int i = 0; i < DIM; i++)
			{
				for(int j=0;j < DIM;j++)
				{
					if(i==j) a[i][j]=0;
					else a[i][j] = x;
				}
			}
		}
	}
};

state operator + (state A, state B) 
{
	state C;
	for(int i=0;i<DIM;i++)
	{
		for(int j=0;j<DIM;j++)
		{
			C[i][j] = INF;
		}
		for(int j=0;j<DIM;j++)
		{
			for(int k=0;k<DIM;k++)
			{
				C[i][k] = min(C[i][k], A[j][k] + B[i][j]);
			}
		}
	}
	return C;
}

state st[263000];

void build(int n) 
{ 
	for(int i = n - 1; i > 0; --i) 
	{
		st[i] = st[i<<1] + st[i<<1|1];
	}
}

void modify(int n, int p, state value) 
{
	for(st[p += n] = value; p >>= 1; ) 
	{
		st[p] = st[p<<1] + st[p<<1|1];
	}
}

state construct(int i)
{
	state cur;
	for(int j=0;j<DIM;j++){for(int k=0;k<DIM;k++){cur[j][k]=INF;}}
	for(int j=0;j<DIM;j++)
	{
		for(int k=0;k<DIM;k++)
		{
			if(paths[a[i-1]][a[i]][j].se!=-1&&paths[a[i]][a[i+1]][k].fi!=-1&&paths[a[i-1]][a[i]][j].se!=paths[a[i]][a[i+1]][k].fi)
			{
				cur[k][j] = min(cur[k][j], D[a[i]][a[i+1]][k]);
			}
		}
	}
	return cur;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i=0;i<263000;i++) st[i] = state(INF);
	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}); W.pb(w); edges.pb({v,u}); W.pb(w); orid[u][v]=orid[v][u]=w;
		adj[u].pb(mp(mp(v,w),i*2)); adj[v].pb(mp(mp(u,w),i*2+1));
		out[u].pb(i*2); out[v].pb(i*2+1);
		in[u].pb(i*2+1); in[v].pb(i*2);
	}
	m*=2;
	for(int i=0;i<m;i++)
	{
		priority_queue<ii,vector<ii>,greater<ii> > pq;
		int s = i;
		pq.push(mp(0,s));
		for(int k=0;k<m;k++) dist[s][k] = INF;
		dist[s][s] = 0;
		while(!pq.empty())
		{
			ll d=pq.top().fi; int u = pq.top().se; pq.pop();
			int vertex = edges[u].se; int edgeno = u;
			for(auto k:adj[vertex])
			{
				int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
				if(id/2==edgeno/2) continue;
				int u1 = edges[id].fi; int v1 = edges[id].se;
				assert(u1==vertex);
				if(dist[s][id]>d)
				{
					dist[s][id] = d;
					pq.push(mp(d+w, id));
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(i==j) continue;
			ll mn=INF; ii cur=mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][0] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[k].se!=paths[i][j][0].fi&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&j!=paths[i][j][0].fi)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][1] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[k].se!=paths[i][j][0].fi&&edges[l].fi!=paths[i][j][1].se&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&j!=paths[i][j][0].fi&&i!=paths[i][j][1].se)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][2] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&i!=paths[i][j][0].se)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][3] = mn;
			paths[i][j].pb(cur);
			mn = INF; cur = mp(-1,-1);
			for(int k:out[i])
			{
				for(int l:in[j])
				{
					if(edges[k].se!=paths[i][j][3].fi&&edges[l].fi!=paths[i][j][0].se&&dist[k][l]+W[k]+W[l]<mn)
					{
						mn=dist[k][l]+W[k]+W[l];
						cur=mp(edges[k].se, edges[l].fi);
					}
				}
			}
			if(orid[i][j]>0)
			{
				if(orid[i][j]<mn&&j!=paths[i][j][3].fi&&i!=paths[i][j][0].se)
				{
					mn=orid[i][j];
					cur=mp(j,i);
				}
			}
			D[i][j][4] = mn;
			paths[i][j].pb(cur);
		}
	}
	for(int i=0;i<L;i++)
	{
		cin>>a[i]; a[i]--;
	}
	ll BIGL = 1;
	while(BIGL<L-2) BIGL*=2;
	for(int i=1;i+1<L;i++)
	{
		st[BIGL+i-1] = construct(i);
	}
	build(BIGL);
	for(int zz=0;zz<q;zz++)
	{
		int y,z; cin>>y>>z; y--; z--; a[y]=z;
		if(y>=1&&y+1<L)
		{
			modify(BIGL, y-1, construct(y));
		}
		if(y>=2&&y<L)
		{
			modify(BIGL, y-2, construct(y-1));
		}
		if(y+2<L)
		{
			modify(BIGL, y, construct(y+1));
		}
		vector<ll> dp;
		for(int i=0;i<5;i++) dp.pb(D[a[0]][a[1]][i]);
		ll ans = INF;
		for(int i=0;i<5;i++)
		{
			for(int j=0;j<5;j++)
			{
				ans = min(ans, dp[j] + st[1][i][j]);
			}
		}
		if(ans>=INF) ans=-1;
		cout<<ans<<'\n';
	}
}

Compilation message (stderr)

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:143:9: warning: unused variable 'v' [-Wunused-variable]
     int v = k.fi.fi; ll w = k.fi.se; int id = k.se;
         ^
wild_boar.cpp:145:32: warning: unused variable 'v1' [-Wunused-variable]
     int u1 = edges[id].fi; int v1 = edges[id].se;
                                ^~

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