Submission #62211

#	Time	Username	Problem	Language	Result	Execution time	Memory
62211		cki86201	Wild Boar (JOI18_wild_boar)	C++11	100 / 100	16440 ms	842416 KiB

wild_boar

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

typedef pair<ll, int> pli;

int N, M, T, L;
t3 edgen[4040];
int edgec[2020][2020];
vector <pii> IE[2020];
vector <int> nume[2020];
vector <int> numl[2020], numr[2020];
vector <pii> E[20020];
int cs;
void addedge(int x, int y, int c) {
	E[x].pb(pii(c, y));
}

ll dis[4040][4040], dtemp[12020];
int X[100010];
pii query[100010];

typedef pair<ll, pii> plp;

void updplp(plp &a, plp &b) {
	if(a.Fi > b.Fi) a = b;
	else if(a.Fi == b.Fi) {
		a.Se.Fi = min(a.Se.Fi, b.Se.Fi);
		a.Se.Se = min(a.Se.Se, b.Se.Se);
	}
}

ll Val[2020][2020][4][4];
int Idx_l[2020][2020][4];
int Idx_r[2020][2020][4];

struct node {
	node(){}
	node(int s, int e) {
		si = sj = 0;
		rep(a, 4) if(Idx_l[s][e][a] != -1) ++si;
		rep(a, 4) if(Idx_r[s][e][a] != -1) ++sj;
		rep(a, si) rep(b, sj) V[a][b] = Val[s][e][a][b];
		rep(a, sj) ir[a] = Idx_r[s][e][a];
		rep(a, si) il[a] = Idx_l[s][e][a];
	}
	ll V[4][4];
	int ir[4], il[4];
	int si, sj;
	void init() {
		rep(i, 4) ir[i] = il[i] = -1;
		rep(i, 4) rep(j, 4) V[i][j] = 1e18;
	}
	ll Get() {
		ll res = 1e18;
		rep(i, 4) rep(j, 4) res = min(res, V[i][j]);
		return res;
	}
};

node merge(const node &lhs, const node &rhs) {
	node res; res.init();
	rep(i, lhs.si) res.il[i] = lhs.il[i]; res.si = lhs.si;
	rep(i, rhs.sj) res.ir[i] = rhs.ir[i]; res.sj = rhs.sj;
	rep(i, lhs.si) if(lhs.il[i] != -1) {
		rep(j, lhs.sj) if(lhs.ir[j] != -1) {
			ll v1 = lhs.V[i][j];
			if(v1 == 1e18) continue;
			rep(k, rhs.si) if(rhs.il[k] != -1 && rhs.il[k] != lhs.ir[j]) {
				rep(l, rhs.sj) if(rhs.ir[l] != -1) {
					if(res.V[i][l] > rhs.V[k][l] + v1) {
						res.V[i][l] = rhs.V[k][l] + v1;
					}
				}
			}
		}
	}
	return res;
}

node Tr[1<<18];

void Init(int rt, int l, int r) {
	if(l == r) {
		Tr[rt] = node(X[l], X[l+1]);
		return;
	}
	int m = (l + r) >> 1;
	Init(rt<<1, l, m);
	Init(rt<<1|1, m+1, r);
	Tr[rt] = merge(Tr[rt<<1], Tr[rt<<1|1]);
}

void update(int rt, int l, int r, int x) {
	if(l == r) {
		Tr[rt] = node(X[l], X[l+1]);
		return;
	}
	int m = (l + r) >> 1;
	if(x <= m) update(rt<<1, l, m, x);
	else update(rt<<1|1, m+1, r, x);
	Tr[rt] = merge(Tr[rt<<1], Tr[rt<<1|1]);
}

int main() {
	memset(edgec, -1, sizeof edgec);
	memset(Idx_l, -1, sizeof Idx_l);
	memset(Idx_r, -1, sizeof Idx_r);
	scanf("%d%d%d%d", &N, &M, &T, &L);
	rep(i, M) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		edgen[i<<1] = t3(x, y, z);
		edgec[x][y] = i<<1;
		edgen[i<<1|1] = t3(y, x, z);
		edgec[y][x] = i<<1|1;
		nume[x].pb(cs++);
		nume[y].pb(cs++);
		IE[x].pb(pii(z, y));
		IE[y].pb(pii(z, x));
	}
	for(int i=1;i<=N;i++) {
		int l = szz(IE[i]);
		numl[i].resize(l);
		numr[i].resize(l);
		rep(j, l) numl[i][j] = cs++;
		rep(j, l) numr[i][j] = cs++;
		for(int j=1;j<l;j++) {
			int x = numl[i][j-1], y = numl[i][j];
			addedge(y, x, 0);
			x = numr[i][j-1], y = numr[i][j];
			addedge(x, y, 0);
		}
		rep(j, l) {
			addedge(numl[i][j], nume[i][j], 0);
			addedge(numr[i][j], nume[i][j], 0);
		}
		rep(j, l) {
			int x = nume[i][j] ^ 1, len = get<2>(edgen[x]);
			if(j) addedge(x, numl[i][j-1], len);
			if(j < l-1) addedge(x, numr[i][j+1], len);
		}
	}
	rep(st, 2*M) {
		rep(i, cs) dtemp[i] = 1e18;
		dtemp[st] = 0;
		priority_queue <pli, vector<pli>, greater<pli> > pq;
		pq.push(pli(0, st));
		while(!pq.empty()) {
			pli t = pq.top(); pq.pop();
			if(dtemp[t.Se] != t.Fi) continue;
			for(pii e : E[t.Se]) {
				if(t.Fi + e.Fi < dtemp[e.Se]) {
					dtemp[e.Se] = t.Fi + e.Fi;
					pq.push(pli(dtemp[e.Se], e.Se));
				}
			}
		}
		rep(i, 2*M) dis[st][i] = dtemp[i];
	}
	
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) rep(a, 4) rep(b, 4) Val[i][j][a][b] = 1e18;
	
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
		int si = szz(IE[i]);
		int sj = szz(IE[j]);
		vector <vector <plp> > mn[4];
		vector <vector <ll> > val;
		rep(a, 4) {
			mn[a].resize(si);
			val.resize(si);
			rep(b, si) mn[a][b].resize(sj), val[b].resize(sj);
		}
		
		rep(k, si) {
			int eidx = nume[i][k];
			rep(l, sj) {
				int fidx = nume[j][l] ^ 1;
				plp pp = plp(dis[eidx][fidx] + get<2>(edgen[fidx]), pii(k, l));
				rep(t, 4) mn[t][k][l] = pp;
				val[k][l] = pp.Fi;
			}
		}
		rep(k, si) for(int l=1;l<sj;l++) for(int a : {0, 2}) updplp(mn[a][k][l], mn[a][k][l-1]);
		rep(k, si) for(int l=sj-2;l>=0;l--) for(int a : {1, 3}) updplp(mn[a][k][l], mn[a][k][l+1]);
		rep(l, sj) for(int k=1;k<si;k++) for(int a : {0, 1}) updplp(mn[a][k][l], mn[a][k-1][l]);
		rep(l, sj) for(int k=si-2;k>=0;k--) for(int a : {2, 3}) updplp(mn[a][k][l], mn[a][k+1][l]);
		set <int> idx_i, idx_j;
		rep(k, si) rep(l, sj) {
			plp r = plp(1e18, pii(-1, -1));
			if(k > 0 && l > 0) updplp(r, mn[0][k-1][l-1]);
			if(k > 0 && l < sj - 1) updplp(r, mn[1][k-1][l+1]);
			if(k < si - 1 && l > 0) updplp(r, mn[2][k+1][l-1]);
			if(k < si - 1 && l < sj - 1) updplp(r, mn[3][k+1][l+1]);
			if(r.Se.Fi != -1) idx_i.insert(r.Se.Fi);
			if(r.Se.Se != -1) idx_j.insert(r.Se.Se);
		}
		rep(k, si) {
			plp r = plp(1e18, pii(-1, -1));
			if(k > 0) updplp(r, mn[0][k-1][sj-1]);
			if(k < si - 1) updplp(r, mn[2][k+1][sj-1]);
			if(r.Se.Fi != -1) idx_i.insert(r.Se.Fi);
			if(r.Se.Se != -1) idx_j.insert(r.Se.Se);
		}
		rep(l, sj) {
			plp r = plp(1e18, pii(-1, -1));
			if(l > 0) updplp(r, mn[0][si-1][l-1]);
			if(l < sj - 1) updplp(r, mn[1][si-1][l+1]);
			if(r.Se.Fi != -1) idx_i.insert(r.Se.Fi);
			if(r.Se.Se != -1) idx_j.insert(r.Se.Se);
		}
		plp r = plp(1e18, pii(-1, -1));
		updplp(r, mn[0][si-1][sj-1]);
		if(r.Se.Fi != -1) idx_i.insert(r.Se.Fi);
		if(r.Se.Se != -1) idx_j.insert(r.Se.Se);
		vector <int> vi, vj;
		for(int e : idx_i) vi.pb(e);
		for(int e : idx_j) vj.pb(e);
		rep(a, szz(vi)) Idx_l[i][j][a] = IE[i][vi[a]].Se;
		rep(a, szz(vj)) Idx_r[i][j][a] = IE[j][vj[a]].Se;
		rep(a, szz(vi)) rep(b, szz(vj)) {
			Val[i][j][a][b] = val[vi[a]][vj[b]];
		}
	}
	
	for(int i=1;i<=L;i++) scanf("%d", X+i);
	for(int i=1;i<=T;i++) {
		int x, y; scanf("%d%d", &x, &y);
		query[i] = pii(x, y);
	}
	
	Init(1, 1, L - 1);
	for(int i=1;i<=T;i++) {
		int x = query[i].Fi;
		int y = query[i].Se;
		X[x] = y;
		if(x > 1) update(1, 1, L - 1, x - 1);
		if(x < L) update(1, 1, L - 1, x);
		ll val = Tr[1].Get();
		if(val >= 1e18) puts("-1");
		else printf("%lld\n", val);
	}

	return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'node merge(const node&, const node&)':
wild_boar.cpp:25:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i, n) for(int i=0;i<n;i++)
                   ^
wild_boar.cpp:90:2: note: in expansion of macro 'rep'
  rep(i, lhs.si) res.il[i] = lhs.il[i]; res.si = lhs.si;
  ^~~
wild_boar.cpp:90:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  rep(i, lhs.si) res.il[i] = lhs.il[i]; res.si = lhs.si;
                                        ^~~
wild_boar.cpp:25:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i, n) for(int i=0;i<n;i++)
                   ^
wild_boar.cpp:91:2: note: in expansion of macro 'rep'
  rep(i, rhs.sj) res.ir[i] = rhs.ir[i]; res.sj = rhs.sj;
  ^~~
wild_boar.cpp:91:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  rep(i, rhs.sj) res.ir[i] = rhs.ir[i]; res.sj = rhs.sj;
                                        ^~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &M, &T, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:253:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=L;i++) scanf("%d", X+i);
                        ~~~~~^~~~~~~~~~~
wild_boar.cpp:255:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

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