Submission #336738

#	Time	Username	Problem	Language	Result	Execution time	Memory
336738		amoo_safar	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	5963 ms	472696 KiB

wild_boar

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 4e3 + 10;
const int K = 1e5 + 10;

const ll Inf = 2242545357980376863LL;
const ll Log = 30;

typedef pair<int, int> pii;

vector<int> G[N], I[N];
int fr[N], to[N], W[N], m = 0;

ll dis[N][N];
int deg[N];
void DJIK(int id){
	memset(dis[id], 31, sizeof dis[id]);
	memset(deg, 0, sizeof deg);
	set<pair<ll, int>> st;
	dis[id][id] = 0;
	
	st.insert({0, id});

	while(!st.empty()){
		int beg = st.begin() -> S; st.erase(st.begin());
		if(deg[to[beg]] >= 2) continue;
		deg[to[beg]] ++;

		for(auto nx : G[to[beg]]){
			if((nx ^ 1) == beg) continue;
			if(dis[id][nx] > dis[id][beg] + W[nx]){
				// cerr << "^^ " << id << ' ' << nx << '\n';
				st.erase({dis[id][nx], nx});
				dis[id][nx] = dis[id][beg] + W[nx];
				st.insert({dis[id][nx], nx});
			}
		}
	}
}

typedef pair<ll, pii> path;

struct node {
	path ans;
	path fa, best_a;
	path fb, best_b;
};
path Get(int u, int v, int fu, int fv){
	path res = {Inf, {-2, -2}};
	for(auto out_u : G[u]){
		if(out_u == fu) continue;
		for(auto in_v : I[v]){
			if(in_v == fv) continue;
			res = min(res, path(dis[out_u][in_v] + W[out_u], {out_u, in_v}));
		}
	}
	return res;
}

node base[N][N];

vector<path> lc, rc;
path Get(int fu, int fv){
	path res = {Inf, {-2, -2}};
	for(auto [ln_l, p_l] : lc){
		if(p_l.F == fu) continue;
		for(auto [ln_r, p_r] : rc){
			if(p_r.S == fv) continue;
			if((p_l.S ^ 1) == p_r.F) continue;
			res = min(res, path(ln_l + ln_r, {p_l.F, p_r.S}));
		}
	}
	return res;
}
node Merge(node& L, node& R){
	lc = {L.ans, L.fa, L.best_a, L.fb, L.best_b};
	rc = {R.ans, R.fa, R.best_a, R.fb, R.best_b};
	node res;
	res.ans = Get(-1, -1);
	// cerr << "!$#@$  " << res.ans.F << '\n';
	int a = res.ans.S.F;
	int b = res.ans.S.S;
	res.fa = Get(a, -1);
	res.best_a = Get(a, res.fa.S.S);

	res.fb = Get(-1, b);
	res.best_b = Get(res.fb.S.F, b);
	return res;
}

node seg[K << 2];

ll A[K];

void Build(int id, int L, int R){
	if(L + 1 == R){
		seg[id] = base[A[L]][A[L + 1]];
		return ;
	}
	int mid = (L + R) >> 1;
	Build(id << 1, L, mid);
	Build(id << 1 | 1, mid, R);
	seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
}

void Change(int id, int idx, pii x, int L, int R){
	if(L + 1 == R){
		seg[id] = base[x.F][x.S];
		return ;
	}
	int mid = (L + R) >> 1;
	if(idx < mid){
		Change(id << 1, idx, x, L, mid);
	} else {
		Change(id << 1 | 1, idx, x, mid, R);
	}
	seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, _m, T, L;
	cin >> n >> _m >> T >> L;

	for(int i = 0; i < _m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		fr[m] = u, to[m] = v, W[m] = w; G[u].pb(m); I[v].pb(m); m ++;
		fr[m] = v, to[m] = u, W[m] = w; G[v].pb(m); I[u].pb(m); m ++;
	}
	for(int i = 0; i < m; i++) DJIK(i);
	// debug(dis[0][2]);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			base[i][j].ans = Get(i, j, -1, -1);
			// cerr << "! " << i << " " << j << " -> " << base[i][j].ans.F << '\n';
			int a = base[i][j].ans.S.F;
			int b = base[i][j].ans.S.S;
			base[i][j].fa = Get(i, j, a, -1);
			// cerr << "!!! " << i << " " << j << " -> " << base[i][j].fa.F << '\n';
			
			base[i][j].best_a = Get(i, j, a, base[i][j].fa.S.S);
			
			base[i][j].fb = Get(i, j, -1, b);
			base[i][j].best_b = Get(i, j, base[i][j].fb.S.F, b);		
		}
	}
	for(int i = 1; i <= L; i++)
		cin >> A[i];
	Build(1, 1, L);
	// cerr << "ANS : " << seg[1].ans.F << '\n';

	for(int i = 1; i <= T; i++){
		int idx, nw;
		cin >> idx >> nw;
		A[idx] = nw;
		if(idx)
			Change(1, idx - 1, pii(A[idx - 1], A[idx]), 1, L);
		if(idx < L)
			Change(1, idx, pii(A[idx], A[idx + 1]), 1, L);
		cout << (seg[1].ans.F >= Inf/2 ? -1 : seg[1].ans.F) << '\n';
	}
	return 0;
}
/*
3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
1
3 1

*/

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