oj.uz

Submission #223032

# Submission time Handle Problem Language Result Execution time Memory
223032 2020-04-14T14:07:06 Z patrikpavic2 Wild Boar (JOI18_wild_boar) C++17
100 / 100
 4486 ms 636864 KB 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < ll, pair < int, int > > pth;
typedef vector < pth > vp;

const ll INF = 1e18;
const int N = 2e3 + 50;
const int OFF = (1 << 17);

inline void mnozi(const vp &A,const vp &B, vp &C){
	C.clear();
	for(pth L : A){
		for(pth R : B){
			if((L.Y.Y ^ 1) != R.Y.X)
				C.PB({L.X + R.X, {L.Y.X, R.Y.Y}});		
		}
	}
}

inline void skrati(vp &A){
	if(!A.size()) return;
	pth min00 = A[0];
	for(pth nxt : A) min00 = min(nxt, min00);
	pth min11 = {INF, {-1, -1}};
	pth min10 = min11, min01 = min11;
	for(pth nxt : A){
		if(nxt.Y.X != min00.Y.X && nxt.Y.Y != min00.Y.Y)
			min11 = min(min11, nxt);
	}
	for(pth nxt : A){
		if(nxt.Y.X != min00.Y.X && nxt.Y.Y != min11.Y.Y)
			min01 = min(min01, nxt);
		if(nxt.Y.X != min11.Y.X && nxt.Y.Y != min00.Y.Y)
			min10 = min(min10, nxt);
	}
	A.clear();
	A.PB(min00);
	if(min11.X != INF) A.PB(min11);
	if(min10.X != INF) A.PB(min10);
	if(min01.X != INF) A.PB(min01);
}

vp tour[2 * OFF], prec[N][N];
int Q[OFF], dobar[2 * OFF];
int u[2 * N], v[2 * N], cost[2 * N];
ll dis[2 * N][2 * N];
priority_queue < pair < ll, int > > S;
int rlx[2 * N];
vector < int > iz[N], uu[N];
int n, m, q, l;

void update(int i){
	if(i < 0 || i >= l - 1) return;
	tour[OFF + i] = prec[Q[i]][Q[i + 1]];
	for(i = (i + OFF) / 2; i ; i /= 2){
		if(!dobar[2 * i + 1]){
			tour[i] = tour[2 * i];
			continue;
		}
		mnozi(tour[2 * i], tour[2 * i + 1], tour[i]);
		skrati(tour[i]);
	}	
}

void dijkstra(int st){
	memset(rlx, -1, sizeof(rlx)); 
	//printf("st je %d --%d--> %d\n", u[st], cost[st], v[st]);
	for(int i = 0;i < 2 * N;i++) dis[st][i] = INF;
	dis[st][st] = cost[st]; S.push({cost[st], st});
	for(;!S.empty();){
		int cur = S.top().Y; S.pop();
		//printf("dis %d ---> %d je %lld\n", st, cur, dis[st][cur]);
		if(rlx[v[cur]] == -2 || (rlx[v[cur]] == (cur ^ 1))) continue;
		if(rlx[v[cur]] != -1){
			int nxt = rlx[v[cur]];
			if(dis[st][nxt] > dis[st][cur] + (ll)cost[nxt]){
				dis[st][nxt] = dis[st][cur] + (ll)cost[nxt];
				S.push({-dis[st][nxt], nxt});
			}
			rlx[v[cur]] = -2;
			continue;
		}
		rlx[v[cur]] = cur ^ 1;
		for(int nxt : iz[v[cur]]){
			if(nxt == (cur ^ 1)) continue;
			if(dis[st][nxt] > dis[st][cur] + (ll)cost[nxt]){
				dis[st][nxt] = dis[st][cur] + (ll)cost[nxt];
				S.push({-dis[st][nxt], nxt});
			}
		}
	}
}

void ispisi(const vp &A){
	for(pth tmp : A) 
		printf(" %d ---%lld--> %d;   ", tmp.Y.X, tmp.X, tmp.Y.Y);
	printf("\n");
}

void namjesti(){
	for(int i = 0;i < 2 * m;i++)
		dijkstra(i);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			for(int poc : iz[i])
				for(int krj : uu[j])
					//if(dis[poc][krj] != INF)
						prec[i][j].PB({dis[poc][krj], {poc, krj}});
			skrati(prec[i][j]);
			//printf("PREC[ %d ][ %d ] : ", i, j); ispisi(prec[i][j]);
			
		}
	}
	for(int i = 0;i + 1 < l;i++){
		tour[OFF + i] = prec[Q[i]][Q[i + 1]];
		dobar[OFF + i] = 1;
	}
	for(int i = OFF - 1; i ; i--){
		dobar[i] = dobar[2 * i] | dobar[2 * i + 1];
		if(!dobar[2 * i + 1]){
			tour[i] = tour[2 * i];
			continue;
		}
		//printf("MNOZIM tour[%d] : ", 2 * i); ispisi(tour[2 * i]);
		//printf("MNOZIM tour[%d] : ", 2 * i + 1); ispisi(tour[2 * i + 1]);
		mnozi(tour[2 * i], tour[2 * i + 1], tour[i]);
		//printf("UMNOZAK je : "); ispisi(tour[i]);
		skrati(tour[i]);
		//printf("SKRACENO je : "); ispisi(tour[i]);
	}
	//printf("%lld\n", tour[1][0].X);
}

int main(){
	scanf("%d%d%d%d", &n, &m, &q, &l);
	for(int i = 0;i < 2 * m;i += 2){
		scanf("%d%d%d", u + i, v + i, cost + i);
		u[i + 1] = v[i], v[i + 1] = u[i], cost[i + 1] = cost[i];
		iz[u[i]].PB(i); iz[u[i + 1]].PB(i + 1);
		uu[v[i]].PB(i); uu[v[i + 1]].PB(i + 1);
	}
	for(int i = 0;i < l;i++)
		scanf("%d", Q + i);
	namjesti();
	for(;q--;){
		int tko, gdje; scanf("%d%d", &gdje, &tko);
		Q[--gdje] = tko;
		update(gdje - 1); update(gdje);
		if(!tour[1].size())
			printf("-1\n");
		else
			printf("%lld\n", tour[1][0].X);
	}
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:146: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, &q, &l);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", u + i, v + i, cost + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", Q + i);
   ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:157:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int tko, gdje; scanf("%d%d", &gdje, &tko);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 72 ms 106488 KB Output is correct
3 Correct 69 ms 106488 KB Output is correct
4 Correct 67 ms 106464 KB Output is correct
5 Correct 65 ms 106488 KB Output is correct
6 Correct 66 ms 106488 KB Output is correct
7 Correct 68 ms 106488 KB Output is correct
8 Correct 67 ms 106508 KB Output is correct
9 Correct 66 ms 106488 KB Output is correct
10 Correct 67 ms 106488 KB Output is correct
11 Correct 74 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 74 ms 106484 KB Output is correct
14 Correct 71 ms 106488 KB Output is correct
15 Correct 67 ms 106488 KB Output is correct
16 Correct 67 ms 106488 KB Output is correct
17 Correct 66 ms 106488 KB Output is correct
18 Correct 67 ms 106492 KB Output is correct
19 Correct 67 ms 106488 KB Output is correct
20 Correct 67 ms 106488 KB Output is correct
21 Correct 66 ms 106292 KB Output is correct
22 Correct 68 ms 106616 KB Output is correct
23 Correct 66 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 67 ms 106488 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 72 ms 106488 KB Output is correct
3 Correct 69 ms 106488 KB Output is correct
4 Correct 67 ms 106464 KB Output is correct
5 Correct 65 ms 106488 KB Output is correct
6 Correct 66 ms 106488 KB Output is correct
7 Correct 68 ms 106488 KB Output is correct
8 Correct 67 ms 106508 KB Output is correct
9 Correct 66 ms 106488 KB Output is correct
10 Correct 67 ms 106488 KB Output is correct
11 Correct 74 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 74 ms 106484 KB Output is correct
14 Correct 71 ms 106488 KB Output is correct
15 Correct 67 ms 106488 KB Output is correct
16 Correct 67 ms 106488 KB Output is correct
17 Correct 66 ms 106488 KB Output is correct
18 Correct 67 ms 106492 KB Output is correct
19 Correct 67 ms 106488 KB Output is correct
20 Correct 67 ms 106488 KB Output is correct
21 Correct 66 ms 106292 KB Output is correct
22 Correct 68 ms 106616 KB Output is correct
23 Correct 66 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 67 ms 106488 KB Output is correct
26 Correct 69 ms 108536 KB Output is correct
27 Correct 103 ms 118520 KB Output is correct
28 Correct 93 ms 118040 KB Output is correct
29 Correct 231 ms 165496 KB Output is correct
30 Correct 229 ms 167160 KB Output is correct
31 Correct 217 ms 166596 KB Output is correct
32 Correct 213 ms 167804 KB Output is correct
33 Correct 238 ms 163576 KB Output is correct
34 Correct 232 ms 163580 KB Output is correct
35 Correct 205 ms 168440 KB Output is correct
36 Correct 218 ms 166264 KB Output is correct
37 Correct 234 ms 164472 KB Output is correct
38 Correct 225 ms 160888 KB Output is correct
39 Correct 226 ms 166136 KB Output is correct
40 Correct 227 ms 161144 KB Output is correct
41 Correct 227 ms 161144 KB Output is correct
42 Correct 207 ms 168824 KB Output is correct
43 Correct 217 ms 158432 KB Output is correct
44 Correct 226 ms 158584 KB Output is correct
45 Correct 161 ms 142712 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 72 ms 106488 KB Output is correct
3 Correct 69 ms 106488 KB Output is correct
4 Correct 67 ms 106464 KB Output is correct
5 Correct 65 ms 106488 KB Output is correct
6 Correct 66 ms 106488 KB Output is correct
7 Correct 68 ms 106488 KB Output is correct
8 Correct 67 ms 106508 KB Output is correct
9 Correct 66 ms 106488 KB Output is correct
10 Correct 67 ms 106488 KB Output is correct
11 Correct 74 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 74 ms 106484 KB Output is correct
14 Correct 71 ms 106488 KB Output is correct
15 Correct 67 ms 106488 KB Output is correct
16 Correct 67 ms 106488 KB Output is correct
17 Correct 66 ms 106488 KB Output is correct
18 Correct 67 ms 106492 KB Output is correct
19 Correct 67 ms 106488 KB Output is correct
20 Correct 67 ms 106488 KB Output is correct
21 Correct 66 ms 106292 KB Output is correct
22 Correct 68 ms 106616 KB Output is correct
23 Correct 66 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 67 ms 106488 KB Output is correct
26 Correct 69 ms 108536 KB Output is correct
27 Correct 103 ms 118520 KB Output is correct
28 Correct 93 ms 118040 KB Output is correct
29 Correct 231 ms 165496 KB Output is correct
30 Correct 229 ms 167160 KB Output is correct
31 Correct 217 ms 166596 KB Output is correct
32 Correct 213 ms 167804 KB Output is correct
33 Correct 238 ms 163576 KB Output is correct
34 Correct 232 ms 163580 KB Output is correct
35 Correct 205 ms 168440 KB Output is correct
36 Correct 218 ms 166264 KB Output is correct
37 Correct 234 ms 164472 KB Output is correct
38 Correct 225 ms 160888 KB Output is correct
39 Correct 226 ms 166136 KB Output is correct
40 Correct 227 ms 161144 KB Output is correct
41 Correct 227 ms 161144 KB Output is correct
42 Correct 207 ms 168824 KB Output is correct
43 Correct 217 ms 158432 KB Output is correct
44 Correct 226 ms 158584 KB Output is correct
45 Correct 161 ms 142712 KB Output is correct
46 Correct 274 ms 159992 KB Output is correct
47 Correct 2943 ms 580348 KB Output is correct
48 Correct 3019 ms 593260 KB Output is correct
49 Correct 3096 ms 612060 KB Output is correct
50 Correct 3037 ms 600832 KB Output is correct
51 Correct 3033 ms 597532 KB Output is correct
52 Correct 3399 ms 620536 KB Output is correct
53 Correct 3361 ms 623636 KB Output is correct
54 Correct 3370 ms 619080 KB Output is correct
55 Correct 3334 ms 622176 KB Output is correct
56 Correct 3351 ms 623096 KB Output is correct
57 Correct 3395 ms 622320 KB Output is correct
58 Correct 3299 ms 623224 KB Output is correct
59 Correct 3289 ms 626748 KB Output is correct
60 Correct 3213 ms 623048 KB Output is correct
61 Correct 3182 ms 621432 KB Output is correct
62 Correct 3008 ms 611392 KB Output is correct
63 Correct 2931 ms 600908 KB Output is correct
64 Correct 1487 ms 558240 KB Output is correct
65 Correct 1509 ms 558252 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 72 ms 106488 KB Output is correct
3 Correct 69 ms 106488 KB Output is correct
4 Correct 67 ms 106464 KB Output is correct
5 Correct 65 ms 106488 KB Output is correct
6 Correct 66 ms 106488 KB Output is correct
7 Correct 68 ms 106488 KB Output is correct
8 Correct 67 ms 106508 KB Output is correct
9 Correct 66 ms 106488 KB Output is correct
10 Correct 67 ms 106488 KB Output is correct
11 Correct 74 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 74 ms 106484 KB Output is correct
14 Correct 71 ms 106488 KB Output is correct
15 Correct 67 ms 106488 KB Output is correct
16 Correct 67 ms 106488 KB Output is correct
17 Correct 66 ms 106488 KB Output is correct
18 Correct 67 ms 106492 KB Output is correct
19 Correct 67 ms 106488 KB Output is correct
20 Correct 67 ms 106488 KB Output is correct
21 Correct 66 ms 106292 KB Output is correct
22 Correct 68 ms 106616 KB Output is correct
23 Correct 66 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 67 ms 106488 KB Output is correct
26 Correct 69 ms 108536 KB Output is correct
27 Correct 103 ms 118520 KB Output is correct
28 Correct 93 ms 118040 KB Output is correct
29 Correct 231 ms 165496 KB Output is correct
30 Correct 229 ms 167160 KB Output is correct
31 Correct 217 ms 166596 KB Output is correct
32 Correct 213 ms 167804 KB Output is correct
33 Correct 238 ms 163576 KB Output is correct
34 Correct 232 ms 163580 KB Output is correct
35 Correct 205 ms 168440 KB Output is correct
36 Correct 218 ms 166264 KB Output is correct
37 Correct 234 ms 164472 KB Output is correct
38 Correct 225 ms 160888 KB Output is correct
39 Correct 226 ms 166136 KB Output is correct
40 Correct 227 ms 161144 KB Output is correct
41 Correct 227 ms 161144 KB Output is correct
42 Correct 207 ms 168824 KB Output is correct
43 Correct 217 ms 158432 KB Output is correct
44 Correct 226 ms 158584 KB Output is correct
45 Correct 161 ms 142712 KB Output is correct
46 Correct 274 ms 159992 KB Output is correct
47 Correct 2943 ms 580348 KB Output is correct
48 Correct 3019 ms 593260 KB Output is correct
49 Correct 3096 ms 612060 KB Output is correct
50 Correct 3037 ms 600832 KB Output is correct
51 Correct 3033 ms 597532 KB Output is correct
52 Correct 3399 ms 620536 KB Output is correct
53 Correct 3361 ms 623636 KB Output is correct
54 Correct 3370 ms 619080 KB Output is correct
55 Correct 3334 ms 622176 KB Output is correct
56 Correct 3351 ms 623096 KB Output is correct
57 Correct 3395 ms 622320 KB Output is correct
58 Correct 3299 ms 623224 KB Output is correct
59 Correct 3289 ms 626748 KB Output is correct
60 Correct 3213 ms 623048 KB Output is correct
61 Correct 3182 ms 621432 KB Output is correct
62 Correct 3008 ms 611392 KB Output is correct
63 Correct 2931 ms 600908 KB Output is correct
64 Correct 1487 ms 558240 KB Output is correct
65 Correct 1509 ms 558252 KB Output is correct
66 Correct 164 ms 138872 KB Output is correct
67 Correct 616 ms 264056 KB Output is correct
68 Correct 1726 ms 606712 KB Output is correct
69 Correct 1839 ms 606608 KB Output is correct
70 Correct 1886 ms 613496 KB Output is correct
71 Correct 4073 ms 583324 KB Output is correct
72 Correct 4182 ms 594784 KB Output is correct
73 Correct 4451 ms 628916 KB Output is correct
74 Correct 4447 ms 630920 KB Output is correct
75 Correct 4486 ms 629264 KB Output is correct
76 Correct 4199 ms 613780 KB Output is correct
77 Correct 4125 ms 602976 KB Output is correct
78 Correct 4024 ms 600204 KB Output is correct
79 Correct 4426 ms 634652 KB Output is correct
80 Correct 4353 ms 634616 KB Output is correct
81 Correct 4109 ms 626308 KB Output is correct
82 Correct 4245 ms 636864 KB Output is correct
83 Correct 4042 ms 635080 KB Output is correct
84 Correct 3915 ms 615064 KB Output is correct
85 Correct 2041 ms 564856 KB Output is correct