oj.uz

Submission #223030

# Submission time Handle Problem Language Result Execution time Memory
223030 2020-04-14T14:01:28 Z patrikpavic2 Wild Boar (JOI18_wild_boar) C++17
12 / 100
 94 ms 108608 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]];
			//printf("s %d na %d\n", cur, nxt);
			if(dis[st][nxt] > dis[st][cur] + cost[nxt]){
				dis[st][nxt] = dis[st][cur] + cost[nxt];
				S.push({-dis[st][nxt], nxt});
			}
			rlx[cur] = -2;
			continue;
		}
		rlx[v[cur]] = cur ^ 1;
		for(int nxt : iz[v[cur]]){
			if(nxt == (cur ^ 1)) continue;
			//printf("s %d na %d\n", cur, nxt);
			if(dis[st][nxt] > dis[st][cur] + cost[nxt]){
				dis[st][nxt] = dis[st][cur] + 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:148: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:150: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:156: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:159: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 68 ms 106492 KB Output is correct
3 Correct 68 ms 106488 KB Output is correct
4 Correct 67 ms 106488 KB Output is correct
5 Correct 68 ms 106488 KB Output is correct
6 Correct 67 ms 106488 KB Output is correct
7 Correct 67 ms 106488 KB Output is correct
8 Correct 68 ms 106508 KB Output is correct
9 Correct 68 ms 106492 KB Output is correct
10 Correct 68 ms 106488 KB Output is correct
11 Correct 67 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 72 ms 106488 KB Output is correct
14 Correct 67 ms 106512 KB Output is correct
15 Correct 94 ms 106488 KB Output is correct
16 Correct 69 ms 106488 KB Output is correct
17 Correct 69 ms 106488 KB Output is correct
18 Correct 67 ms 106488 KB Output is correct
19 Correct 68 ms 106488 KB Output is correct
20 Correct 73 ms 106488 KB Output is correct
21 Correct 68 ms 106488 KB Output is correct
22 Correct 68 ms 106492 KB Output is correct
23 Correct 65 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 68 ms 106492 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 68 ms 106492 KB Output is correct
3 Correct 68 ms 106488 KB Output is correct
4 Correct 67 ms 106488 KB Output is correct
5 Correct 68 ms 106488 KB Output is correct
6 Correct 67 ms 106488 KB Output is correct
7 Correct 67 ms 106488 KB Output is correct
8 Correct 68 ms 106508 KB Output is correct
9 Correct 68 ms 106492 KB Output is correct
10 Correct 68 ms 106488 KB Output is correct
11 Correct 67 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 72 ms 106488 KB Output is correct
14 Correct 67 ms 106512 KB Output is correct
15 Correct 94 ms 106488 KB Output is correct
16 Correct 69 ms 106488 KB Output is correct
17 Correct 69 ms 106488 KB Output is correct
18 Correct 67 ms 106488 KB Output is correct
19 Correct 68 ms 106488 KB Output is correct
20 Correct 73 ms 106488 KB Output is correct
21 Correct 68 ms 106488 KB Output is correct
22 Correct 68 ms 106492 KB Output is correct
23 Correct 65 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 68 ms 106492 KB Output is correct
26 Incorrect 69 ms 108608 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 68 ms 106492 KB Output is correct
3 Correct 68 ms 106488 KB Output is correct
4 Correct 67 ms 106488 KB Output is correct
5 Correct 68 ms 106488 KB Output is correct
6 Correct 67 ms 106488 KB Output is correct
7 Correct 67 ms 106488 KB Output is correct
8 Correct 68 ms 106508 KB Output is correct
9 Correct 68 ms 106492 KB Output is correct
10 Correct 68 ms 106488 KB Output is correct
11 Correct 67 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 72 ms 106488 KB Output is correct
14 Correct 67 ms 106512 KB Output is correct
15 Correct 94 ms 106488 KB Output is correct
16 Correct 69 ms 106488 KB Output is correct
17 Correct 69 ms 106488 KB Output is correct
18 Correct 67 ms 106488 KB Output is correct
19 Correct 68 ms 106488 KB Output is correct
20 Correct 73 ms 106488 KB Output is correct
21 Correct 68 ms 106488 KB Output is correct
22 Correct 68 ms 106492 KB Output is correct
23 Correct 65 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 68 ms 106492 KB Output is correct
26 Incorrect 69 ms 108608 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 106104 KB Output is correct
2 Correct 68 ms 106492 KB Output is correct
3 Correct 68 ms 106488 KB Output is correct
4 Correct 67 ms 106488 KB Output is correct
5 Correct 68 ms 106488 KB Output is correct
6 Correct 67 ms 106488 KB Output is correct
7 Correct 67 ms 106488 KB Output is correct
8 Correct 68 ms 106508 KB Output is correct
9 Correct 68 ms 106492 KB Output is correct
10 Correct 68 ms 106488 KB Output is correct
11 Correct 67 ms 106488 KB Output is correct
12 Correct 68 ms 106488 KB Output is correct
13 Correct 72 ms 106488 KB Output is correct
14 Correct 67 ms 106512 KB Output is correct
15 Correct 94 ms 106488 KB Output is correct
16 Correct 69 ms 106488 KB Output is correct
17 Correct 69 ms 106488 KB Output is correct
18 Correct 67 ms 106488 KB Output is correct
19 Correct 68 ms 106488 KB Output is correct
20 Correct 73 ms 106488 KB Output is correct
21 Correct 68 ms 106488 KB Output is correct
22 Correct 68 ms 106492 KB Output is correct
23 Correct 65 ms 106488 KB Output is correct
24 Correct 67 ms 106488 KB Output is correct
25 Correct 68 ms 106492 KB Output is correct
26 Incorrect 69 ms 108608 KB Output isn't correct
27 Halted 0 ms 0 KB -