Submission #524486

#	Time	Username	Problem	Language	Result	Execution time	Memory
524486		AmShZ	Wild Boar (JOI18_wild_boar)	C++11	0 / 100	113 ms	313192 KiB

wild_boar

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <ll, ll>                                    pll;
typedef pair <pll, pll>                                  ppp;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e3 + 10;
const int xm = 1e5 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

struct path{
	int from, to;
	ll dist = INF;
};
struct paths{
	int from, to;
	path a[2][2];
};

int n, m, q, L, a[xm];
ll dis[xn][xn];
priority_queue <pll> pq;
priority_queue <pair <ll, ppp> > pp;
vector <pii> adj[xn];
paths seg[xm << 2], f[xn][xn];

void dijk(int src){
	for (int v = 1; v <= n; ++ v)
		dis[src][v] = INF;
	dis[src][src] = 0;
	pq.push({0, src});
	while (SZ(pq)){
		int v = pq.top().B;
		pq.pop();
		for (pii u : adj[v])
			if (dis[src][v] + u.B < dis[src][u.A])
				dis[src][u.A] = dis[src][v] + u.B, pq.push({- dis[src][u.A], u.A});
	}
}
void upd_paths(paths &x, path &y){
	if (y.from != x.a[0][0].from && y.dist < x.a[1][0].dist)
		x.a[1][0] = y;
	if (y.to != x.a[0][0].to && y.dist < x.a[0][1].dist)
		x.a[0][1] = y;
	if (y.from != x.a[0][0].from && y.to != x.a[0][0].to && y.dist < x.a[1][1].dist)
		x.a[1][1] = y;
}
paths merge(paths &x, paths &y){
	paths z;
	for (int i = 0; i < 2; ++ i){
		for (int j = 0; j < 2; ++ j){
			for (int k = 0; k < 2; ++ k){
				for (int o = 0; o < 2; ++ o){
					if (x.a[i][j].dist == INF || y.a[k][o].dist == INF || x.a[i][j].to == y.a[k][o].from)
						continue;
					path p;
					p.from = x.a[i][j].from;
					p.to = y.a[k][o].to;
					p.dist = x.a[i][j].dist + y.a[k][o].dist;
					if (p.dist < z.a[0][0].dist)
						z.a[0][0] = p;
				}
			}
		}
	}
	for (int i = 0; i < 2; ++ i){
		for (int j = 0; j < 2; ++ j){
			for (int k = 0; k < 2; ++ k){
				for (int o = 0; o < 2; ++ o){
					if (x.a[i][j].dist == INF || y.a[k][o].dist == INF || x.a[i][j].to == y.a[k][o].from)
						continue;
					path p;
					p.from = x.a[i][j].from;
					p.to = y.a[k][o].to;
					p.dist = x.a[i][j].dist + y.a[k][o].dist;
					upd_paths(z, p);
				}
			}
		}
	}
	return z;
}
void build(int id, int l, int r){
	if (r - l == 1){
		seg[id] = f[a[l]][a[r]];
		return;
	}
	int mid = l + r >> 1;
	build(lc, l, mid);
	build(rc, mid, r);
	seg[id] = merge(seg[lc], seg[rc]);
}
void modify(int id, int l, int r, int pos){
	if (r - l == 1){
		seg[id] = f[a[l]][a[r]];
		return;
	}
	int mid = l + r >> 1;
	if (pos - 1 < mid)
		modify(lc, l, mid, pos);
	if (mid <= pos)
		modify(rc, mid, r, pos);
	seg[id] = merge(seg[lc], seg[rc]);
}

int main(){
	fast_io;

	cin >> n >> m >> q >> L;
	while (m --){
		int v, u, w;
		cin >> v >> u >> w;
		adj[v].push_back({u, w});
		adj[u].push_back({v, w});
	}
	for (int v = 1; v <= n; ++ v)
		dijk(v);
	for (int v = 1; v <= n; ++ v){
		for (int u = 1; u <= n; ++ u){
			if (v == u)
				continue;
			f[v][u].from = v;
			f[v][u].to = u;
			f[v][u].a[0][0].dist = dis[v][u];
			f[v][u].a[0][0].from = u;
			f[v][u].a[0][0].to = v;
			for (pii vv : adj[v])
				for (pii uu : adj[u])
					if (dis[vv.A][uu.A] + vv.B + uu.B == dis[v][u])
						f[v][u].a[0][0].from = vv.A, f[v][u].a[0][0].to = uu.A;
			pp.push({0, {{v, u}, {0, 0}}});
		}
	}
	while (SZ(pp)){
		int v = pp.top().B.A.A;
		int u = pp.top().B.A.B;
		int f1 = pp.top().B.B.A;
		int f2 = pp.top().B.B.B;
		pp.pop();
		for (pii x : adj[u]){
			if (x.A == f[v][u].a[f1][f2].to)
				continue;
			path p = f[v][u].a[f1][f2];
			p.to = u;
			p.dist += x.B;
			if (p.dist < f[v][x.A].a[f1][0].dist && p.to == f[v][x.A].a[0][0].to){
				f[v][x.A].a[f1][0] = p;
				pp.push({- p.dist, {{v, x.A}, {f1, 0}}});
			}
			if (p.dist < f[v][x.A].a[f1][1].dist && p.to != f[v][x.A].a[0][0].to){
				f[v][x.A].a[f1][1] = p;
				pp.push({- p.dist, {{v, x.A}, {f1, 1}}});
			}
		}
		for (pii x : adj[v]){
			if (x.A == f[v][u].a[f1][f2].from)
				continue;
			path p = f[v][u].a[f1][f2];
			p.from = v;
			p.dist += x.B;
			if (p.dist < f[x.A][u].a[0][f2].dist && p.from == f[x.A][u].a[0][0].from){
				f[x.A][u].a[0][f2] = p;
				pp.push({- p.dist, {{x.A, u}, {0, f2}}});
			}
			if (p.dist < f[x.A][u].a[1][f2].dist && p.from != f[x.A][u].a[0][0].from){
				f[x.A][u].a[1][f2] = p;
				pp.push({- p.dist, {{x.A, u}, {1, f2}}});
			}
		}
	}
	for (int i = 1; i <= L; ++ i)
		cin >> a[i];
	build(1, 1, L);
	while (q --){
		int x, y;
		cin >> x >> y;
		a[x] = y;
		modify(1, 1, L, x);
		if (seg[1].a[0][0].dist < INF)
			cout << seg[1].a[0][0].dist << endl;
		else
			cout << - 1 << endl;
	}

	return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'void build(int, int, int)':
wild_boar.cpp:113:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |  int mid = l + r >> 1;
      |            ~~^~~
wild_boar.cpp: In function 'void modify(int, int, int, int)':
wild_boar.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |  int mid = l + r >> 1;
      |            ~~^~~

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