Submission #656744

#	Time	Username	Problem	Language	Result	Execution time	Memory
656744		haojiandan	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	8114 ms	523472 KiB

wild_boar

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int maxn=4010;
int n,m;
int Q,L;
ll dis[maxn][maxn],w[maxn];
pair<int,int> E[maxn];
ll mn[maxn][maxn][5];
pair<int,int> rem[maxn][maxn][5];
vector<int> in[maxn],out[maxn];
int id[maxn][maxn]; bool vis[maxn];
int d[maxn]; ll dp[2][maxn];
priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > q;
struct Matrix {
	ll d[5][5];
	friend Matrix operator + (Matrix t1,Matrix t2) {
		Matrix res;
		for (int i=0;i<5;i++) for (int j=0;j<5;j++) {
			res.d[i][j]=INF;
			for (int k=0;k<5;k++) res.d[i][j]=min(t1.d[i][k]+t2.d[k][j],res.d[i][j]);
		}
		return res;
	}
} tr[100010*4];
void change(int x,int l,int r,int root,Matrix A) {
	if (l==r) { tr[root]=A; return; }
	int mid=(l+r)>>1;
	if (x<=mid) change(x,l,mid,root<<1,A);
	else change(x,mid+1,r,root<<1|1,A);
	tr[root]=tr[root<<1]+tr[root<<1|1];
}
void init(int i) {
	if (i>=3&&i<=L); else return;
	Matrix A;
	for (int i=0;i<5;i++) for (int j=0;j<5;j++) A.d[i][j]=INF;
	for (int j=0;j<5;j++) for (int k=0;k<5;k++) if (mn[d[i-1]][d[i]][k]<INF) {
		if (rem[d[i-2]][d[i-1]][j].second==rem[d[i-1]][d[i]][k].first) continue;
		A.d[j][k]=mn[d[i-1]][d[i]][k];
	}
	change(i,3,L,1,A);
}
int main() {
	read(n),read(m);
	read(Q),read(L);
	int tot=0;
	for (int i=1;i<=m;i++) {
		int x,y; read(x),read(y);
		id[x][y]=id[y][x]=i;
		read(w[i]);
		
		E[tot]=MP(x,y);
		out[x].push_back(tot),in[y].push_back(tot);
		tot++;
		E[tot]=MP(y,x);
		out[y].push_back(tot),in[x].push_back(tot);
		tot++;
	}
	for (int i=0;i<tot;i++) {
		q.push(MP(0,i));
		for (int j=0;j<tot;j++) dis[i][j]=INF,vis[j]=0;
		dis[i][i]=0;
		while (!q.empty()) {
			int x=q.top().second; q.pop();
			if (vis[x]) continue;
			vis[x]=1;
			int u=E[x].second;
			for (int &id : out[u]) {
				int v=E[id].second;
				if ((id^x)==1) continue;
				assert(id!=x);
				ll w=::w[::id[u][v]];
				assert(id/2+1==::id[u][v]);
				if (dis[i][id]>dis[i][x]+w) dis[i][id]=dis[i][x]+w,q.push(MP(dis[i][id],id));
			}
		}
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j) {
		ll *mn=::mn[i][j];
		pair<int,int> *rem=::rem[i][j];
		for (int k=0;k<5;k++) mn[k]=INF;
		for (int k=0;k<5;k++) {
			for (int &x : out[i]) for (int &y : in[j]) {
				if (dis[x][y]+w[x/2+1]<mn[k]) {
					int A=E[x].second,B=E[y].first;
					if (k==1&&A==rem[0].first) continue;
					if (k==2&&(A==rem[0].first||B==rem[1].second)) continue;
					if (k==3&&B==rem[0].second) continue;
					if (k==4&&(B==rem[0].second||A==rem[3].first)) continue;
					mn[k]=dis[x][y]+w[x/2+1];
					rem[k]=MP(A,B);
				}
			}
			if (id[i][j]&&w[id[i][j]]<mn[k]) {
				int A=j,B=i;
				if (k==1&&A==rem[0].first) continue;
				if (k==2&&(A==rem[0].first||B==rem[1].second)) continue;
				if (k==3&&B==rem[0].second) continue;
				if (k==4&&(B==rem[0].second||A==rem[3].first)) continue;
				mn[k]=w[id[i][j]];
				rem[k]=MP(A,B);
			}
		}
	}
	for (int i=1;i<=L;i++) read(d[i]);
	for (int i=3;i<=L;i++) init(i);
	while (Q--) {
		int x; read(x),read(d[x]);
		init(x);
		init(x+1);
		init(x+2);
		ll MN[5];
		for (int i=0;i<5;i++) {
			MN[i]=mn[d[1]][d[2]][i];
		}
		ll ans=INF;
		if (L==2) {
			for (int i=0;i<5;i++) ans=min(ans,MN[i]);
		} else {
			Matrix &res=tr[1];
			for (int i=0;i<5;i++) for (int j=0;j<5;j++) ans=min(ans,MN[i]+res.d[i][j]);
		}
		if (ans==INF) ans=-1;
		printf("%lld\n",ans);
	}
	return 0;
}

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