Submission #209307

#	Time	Username	Problem	Language	Result	Execution time	Memory
209307		songc	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	12214 ms	411728 KiB

wild_boar

#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define fi first
#define se second
#define INF (1ll<<60)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, Q, L;
int P[101010];
int num[2020][2020], nm;
LL D[4040][4040];
bool chk[4040];
vector<pii> adj[2020];

struct Path{
	int u, v;
	LL w;
	bool operator<(const Path &r)const{
		return w < r.w;
	}
};
priority_queue<Path> PQ;

struct Node{
	Path p[4];
} C[2020][2020], T[404040];

void dijk(int a, int b){
	PQ.push((Path){a, b, 0});
	D[num[a][b]][num[a][b]]=0;
	while (!PQ.empty()){
		Path T = PQ.top();
		PQ.pop();
		if (chk[num[T.u][T.v]]) continue;
		chk[num[T.u][T.v]] = true;
		for (pii x : adj[T.u]) if (x.fi != T.v && D[num[a][b]][num[x.fi][T.u]] > -T.w+x.se){
			D[num[a][b]][num[x.fi][T.u]] = -T.w+x.se;
			PQ.push((Path){x.fi, T.u, T.w-x.se});
		}
	}
}

Path add(Path a, Path b){
	return (Path){a.u, b.v, (a.v==b.u)?INF:min(INF,a.w+b.w)};
}

Node add(Node a, Node b){
	Node ret;
	for (int i=0; i<4; i++) ret.p[i].w=INF;
	vector<Path> v;
	for (int i=0; i<4; i++) for (int j=0; j<4; j++) v.pb(add(a.p[i], b.p[j]));
	for (Path x : v) ret.p[0] = min(ret.p[0], x);
	for (Path x : v) if (ret.p[0].u != x.u && ret.p[0].v != x.v) ret.p[1] = min(ret.p[1], x);
	for (Path x : v) if (ret.p[1].u != x.u && ret.p[0].v != x.v) ret.p[2] = min(ret.p[2], x);
	for (Path x : v) if (ret.p[0].u != x.u && ret.p[1].v != x.v) ret.p[3] = min(ret.p[3], x);
	return ret;
}

void init(int id, int s, int e){
	if (s+1 == e){
		T[id] = C[P[s]][P[e]];
		return;
	}
	int mid=(s+e)/2;
	init(id*2, s, mid), init(id*2+1, mid, e);
	T[id] = add(T[id*2], T[id*2+1]);
}

void upd(int id, int s, int e, int t){
	if (e < t || t < s) return;
	if (s+1 == e){
		T[id] = C[P[s]][P[e]];
		return;
	}
	int mid=(s+e)/2;
	upd(id*2, s, mid, t), upd(id*2+1, mid, e, t);
	T[id] = add(T[id*2], T[id*2+1]);
}

int main(){
	scanf("%d %d %d %d", &N, &M, &Q, &L);
	for (int i=1; i<=M; i++){
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		adj[u].pb(pii(v, w)), adj[v].pb(pii(u, w));
	}
	for (int u=1; u<=N; u++) for (pii v : adj[u]) num[u][v.fi]=++nm;
	for (int i=1; i<=nm; i++) for (int j=1; j<=nm; j++) D[i][j] = INF;
	for (int u=1; u<=N; u++) for (pii v : adj[u]){
		memset(chk, false, sizeof chk);
		dijk(u, v.fi);
	}
	for (int i=1; i<=N; i++) for (int j=1; j<=N; j++){
		if (i == j) continue;
		for (int k=0; k<4; k++) C[i][j].p[k].w = INF;
		vector<Path> V;
		for (pii u : adj[i]) for (pii v : adj[j]) V.pb((Path){u.fi, v.fi, D[num[u.fi][i]][num[j][v.fi]]+u.se});
		for (Path x : V) C[i][j].p[0] = min(C[i][j].p[0], x);
		for (Path x : V) if (C[i][j].p[0].u != x.u && C[i][j].p[0].v != x.v) C[i][j].p[1] = min(C[i][j].p[1], x);
		for (Path x : V) if (C[i][j].p[1].u != x.u && C[i][j].p[0].v != x.v) C[i][j].p[2] = min(C[i][j].p[2], x);
		for (Path x : V) if (C[i][j].p[0].u != x.u && C[i][j].p[1].v != x.v) C[i][j].p[3] = min(C[i][j].p[3], x);
	}
	for (int i=1; i<=L; i++) scanf("%d", &P[i]);
	init(1, 1, L);
	while(Q--){
		int a, b;
		scanf("%d %d", &a, &b);
		P[a]=b;
		upd(1, 1, L, a);
		if (T[1].p[0].w >= INF) puts("-1");
		else printf("%lld\n", T[1].p[0].w);
	}
	return 0;
}

Compilation message (stderr)

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:85: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:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:107:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=L; i++) scanf("%d", &P[i]);
                           ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

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