Submission #288687

#	Time	Username	Problem	Language	Result	Execution time	Memory
288687		Blagojce	Wild Boar (JOI18_wild_boar)	C++11	62 / 100	18072 ms	556408 KiB

wild_boar

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e9;
const ll inf = 2e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 4003;
 
const ll A = 911382323;
const ll B = 972663749;

int n, m, t, len;
int a[100005];
vector<int> g[mxn];

int l[mxn], r[mxn], w[mxn];




ll dist[2][mxn][2][mxn];
bool vis[2][mxn][2][mxn];


void dijkstra(int edge, int side){
	pq<pair<ll, pii> > Q;
	Q.push({0, {edge, side}});
	dist[side][edge][side][edge] = 0;
	while(!Q.empty()){
		int e = Q.top().nd.st;
		int s = Q.top().nd.nd;
		Q.pop();
		if(vis[side][edge][s][e]) continue;
		vis[side][edge][s][e] = true;
		
		int node = l[e];
		if(s == 1) node = r[e];
		
		for(auto edge2 : g[node]){
			if(edge2 == e || edge2>=m) continue;
			int side2 = 0;
			if(l[edge2] == node) side2 = 1;
			
			if(dist[side][edge][s][e] + w[edge2] < dist[side][edge][side2][edge2]){
				dist[side][edge][side2][edge2] = dist[side][edge][s][e] + w[edge2];
				Q.push({-dist[side][edge][side2][edge2], {edge2, side2}});
			}
		}
	}
}
	
void prec(){
	fr(i, 0, 2) fr(j, 0, n+m) fr(k, 0, 2)fr(p, 0, n+m) dist[i][j][k][p] = inf;
	fr(i, 0, n){
		for(auto edge : g[i]){
			int side = 0;
			if(r[edge] == i) side = 1;
			dijkstra(edge, side);
		}
	}
}


void solve(){
	cin >> n >> m >> t >> len;
	fr(i, 0, m){
		cin >> l[i] >> r[i] >> w[i];
		--l[i], --r[i];
		g[l[i]].pb(i);
		g[r[i]].pb(i);
	}
	fr(i, 0, n){
		l[i+m] = r[i+m] = i;
		g[i].pb(i+m);
	}
	fr(i, 0, len){
		cin >> a[i];
		--a[i];
	}
	
	prec();
	pair<ll, pii> mi1;
	pair<ll, pii> mi2;
	pair<ll, pii> tmp;
	
	
	vector<pair<ll,pii> > memo[len];
	
	
	
	fr(I, 0, t){
		int p, q;
		cin >> p >> q;
		a[p-1] = q-1;
		
		vector<pair<ll, pii> > v;
		int fst = 1;
		if(I > 0){
			if(p == 1){
				v = {{0, {a[0]+m, 1}}};
			}
			else{
				fst = p-1;
				v = memo[p-1];
			}
		}
		else{
			v = {{0, {a[0]+m, 1}}};
		}
		fr(i, fst, len){
			mi1.st = inf;
			mi2.st = inf;
			memo[i] = v;
			for(auto G : v){
				ll w = G.st;
				int side = G.nd.nd;
				int edge = G.nd.st;
				for(auto e : g[a[i]]){
					if(e >= m) continue;
					
					int s = 0;
					if(a[i] == r[e]) s = 1;
					
					tmp = {min(inf, w + dist[side][edge][s][e]), {e, s}};
					if(tmp.st < mi1.st){
						if(tmp.nd.st != mi1.nd.st){
							mi2 = mi1;
							mi1 = tmp;
						}
						else{
							mi1 = tmp;
						}
					}
					else if(tmp.st < mi2.st){
						if(tmp.nd.st != mi1.nd.st){
							mi2 = tmp;
						}
					}
				}
			}
			if(mi1.st == inf) v = {};
			else if(mi2.st == inf) v = {mi1};
			else v = {mi1, mi2};
		}
		
		ll ans = inf;
		if(!v.empty()) ans = v[0].st;
		
		if(ans == inf) ans = -1;
		cout<<ans<<endl;
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}
/*
5 10 1 10
1 2 8
1 3 5
1 4 2
1 5 1
2 3 7
2 4 9
2 5 6
3 4 10
3 5 10
4 5 6
4
2
4
3
5
3
1
4
3
5
3 5
*/

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