oj.uz

Submission #656744

# Submission time Handle Problem Language Result Execution time Memory
656744 2022-11-08T07:03:49 Z haojiandan Wild Boar (JOI18_wild_boar) C++14
100 / 100
 8114 ms 523472 KB 
// 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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 2 ms 1236 KB Output is correct
27 Correct 288 ms 55468 KB Output is correct
28 Correct 280 ms 55472 KB Output is correct
29 Correct 335 ms 59748 KB Output is correct
30 Correct 333 ms 59636 KB Output is correct
31 Correct 335 ms 59560 KB Output is correct
32 Correct 339 ms 59556 KB Output is correct
33 Correct 365 ms 61312 KB Output is correct
34 Correct 338 ms 61472 KB Output is correct
35 Correct 328 ms 61260 KB Output is correct
36 Correct 333 ms 61324 KB Output is correct
37 Correct 338 ms 61300 KB Output is correct
38 Correct 337 ms 63388 KB Output is correct
39 Correct 323 ms 63308 KB Output is correct
40 Correct 337 ms 63360 KB Output is correct
41 Correct 338 ms 63360 KB Output is correct
42 Correct 315 ms 64668 KB Output is correct
43 Correct 339 ms 65788 KB Output is correct
44 Correct 338 ms 65768 KB Output is correct
45 Correct 303 ms 68620 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 2 ms 1236 KB Output is correct
27 Correct 288 ms 55468 KB Output is correct
28 Correct 280 ms 55472 KB Output is correct
29 Correct 335 ms 59748 KB Output is correct
30 Correct 333 ms 59636 KB Output is correct
31 Correct 335 ms 59560 KB Output is correct
32 Correct 339 ms 59556 KB Output is correct
33 Correct 365 ms 61312 KB Output is correct
34 Correct 338 ms 61472 KB Output is correct
35 Correct 328 ms 61260 KB Output is correct
36 Correct 333 ms 61324 KB Output is correct
37 Correct 338 ms 61300 KB Output is correct
38 Correct 337 ms 63388 KB Output is correct
39 Correct 323 ms 63308 KB Output is correct
40 Correct 337 ms 63360 KB Output is correct
41 Correct 338 ms 63360 KB Output is correct
42 Correct 315 ms 64668 KB Output is correct
43 Correct 339 ms 65788 KB Output is correct
44 Correct 338 ms 65768 KB Output is correct
45 Correct 303 ms 68620 KB Output is correct
46 Correct 178 ms 18212 KB Output is correct
47 Correct 6874 ms 204668 KB Output is correct
48 Correct 5999 ms 239640 KB Output is correct
49 Correct 4756 ms 270920 KB Output is correct
50 Correct 5108 ms 271016 KB Output is correct
51 Correct 5733 ms 271020 KB Output is correct
52 Correct 3448 ms 271404 KB Output is correct
53 Correct 3391 ms 271212 KB Output is correct
54 Correct 3397 ms 271240 KB Output is correct
55 Correct 3514 ms 271020 KB Output is correct
56 Correct 3506 ms 289040 KB Output is correct
57 Correct 3487 ms 308792 KB Output is correct
58 Correct 3425 ms 329716 KB Output is correct
59 Correct 3473 ms 352492 KB Output is correct
60 Correct 3512 ms 376684 KB Output is correct
61 Correct 3733 ms 402344 KB Output is correct
62 Correct 3441 ms 429456 KB Output is correct
63 Correct 3102 ms 458184 KB Output is correct
64 Correct 1587 ms 520104 KB Output is correct
65 Correct 1572 ms 520772 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 724 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 2 ms 1236 KB Output is correct
27 Correct 288 ms 55468 KB Output is correct
28 Correct 280 ms 55472 KB Output is correct
29 Correct 335 ms 59748 KB Output is correct
30 Correct 333 ms 59636 KB Output is correct
31 Correct 335 ms 59560 KB Output is correct
32 Correct 339 ms 59556 KB Output is correct
33 Correct 365 ms 61312 KB Output is correct
34 Correct 338 ms 61472 KB Output is correct
35 Correct 328 ms 61260 KB Output is correct
36 Correct 333 ms 61324 KB Output is correct
37 Correct 338 ms 61300 KB Output is correct
38 Correct 337 ms 63388 KB Output is correct
39 Correct 323 ms 63308 KB Output is correct
40 Correct 337 ms 63360 KB Output is correct
41 Correct 338 ms 63360 KB Output is correct
42 Correct 315 ms 64668 KB Output is correct
43 Correct 339 ms 65788 KB Output is correct
44 Correct 338 ms 65768 KB Output is correct
45 Correct 303 ms 68620 KB Output is correct
46 Correct 178 ms 18212 KB Output is correct
47 Correct 6874 ms 204668 KB Output is correct
48 Correct 5999 ms 239640 KB Output is correct
49 Correct 4756 ms 270920 KB Output is correct
50 Correct 5108 ms 271016 KB Output is correct
51 Correct 5733 ms 271020 KB Output is correct
52 Correct 3448 ms 271404 KB Output is correct
53 Correct 3391 ms 271212 KB Output is correct
54 Correct 3397 ms 271240 KB Output is correct
55 Correct 3514 ms 271020 KB Output is correct
56 Correct 3506 ms 289040 KB Output is correct
57 Correct 3487 ms 308792 KB Output is correct
58 Correct 3425 ms 329716 KB Output is correct
59 Correct 3473 ms 352492 KB Output is correct
60 Correct 3512 ms 376684 KB Output is correct
61 Correct 3733 ms 402344 KB Output is correct
62 Correct 3441 ms 429456 KB Output is correct
63 Correct 3102 ms 458184 KB Output is correct
64 Correct 1587 ms 520104 KB Output is correct
65 Correct 1572 ms 520772 KB Output is correct
66 Correct 329 ms 53012 KB Output is correct
67 Correct 646 ms 132724 KB Output is correct
68 Correct 995 ms 467724 KB Output is correct
69 Correct 1344 ms 468784 KB Output is correct
70 Correct 2182 ms 521148 KB Output is correct
71 Correct 7823 ms 207004 KB Output is correct
72 Correct 6895 ms 242128 KB Output is correct
73 Correct 4360 ms 273848 KB Output is correct
74 Correct 4385 ms 273996 KB Output is correct
75 Correct 4390 ms 273940 KB Output is correct
76 Correct 5515 ms 273260 KB Output is correct
77 Correct 6654 ms 273300 KB Output is correct
78 Correct 8114 ms 273512 KB Output is correct
79 Correct 4375 ms 311696 KB Output is correct
80 Correct 4739 ms 332596 KB Output is correct
81 Correct 5214 ms 354488 KB Output is correct
82 Correct 4652 ms 379324 KB Output is correct
83 Correct 4091 ms 404464 KB Output is correct
84 Correct 3755 ms 460972 KB Output is correct
85 Correct 2334 ms 523472 KB Output is correct