Submission #223032

#	Time	Username	Problem	Language	Result	Execution time	Memory
223032		patrikpavic2	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	4486 ms	636864 KiB

wild_boar

#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 (stderr)

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 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38