Submission #346435

#	Time	Username	Problem	Language	Result	Execution time	Memory
346435		alishahali1382	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	6813 ms	480112 KiB

wild_boar

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, N=2005, M=4005;
typedef array<pair<ll, pii>, 5> DATA;

int n, m, T, L, k, u, v, x, y, t, a, b, ans;
int U[M], V[M], W[M], X[MAXN];
ll dist[M][M];
bool mark[M][M];
DATA F[N][N];
DATA seg[MAXN<<2];
vector<int> G[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;

DATA Merge(DATA X, DATA Y){
	vector<pair<ll, pii>> vec;
	for (int i=0; i<5; i++) for (int j=0; j<5; j++) if (X[i].first+Y[j].first<INF && X[i].second.second!=Y[j].second.first){
		int a=X[i].second.first, b=Y[j].second.second;
		ll w=X[i].first+Y[j].first;
		vec.pb({w, {a, b}});
	}
	DATA Z=F[0][0];
	sort(all(vec));
	if (vec.empty()) return Z;
	Z[0]=vec[0];
	int sz=1, lastx=-1, lasty=-1, tedx=0, tedy=0;
	int x=Z[0].second.first, y=Z[0].second.second;
	for (int i=1; i<vec.size() && sz<5; i++){
		int a=vec[i].second.first, b=vec[i].second.second;
		bool okx=(a!=x && b!=lastx && tedx<2);
		bool oky=(b!=y && a!=lasty && tedy<2);
		if (!okx && !oky) continue ;
		Z[sz++]=vec[i];
		if (okx){
			tedx++;
			lastx=b;
		}
		if (oky){
			tedy++;
			lasty=a;
		}
	}
	return Z;
}
void print(DATA X){
	for (int i=0; i<5 && X[i].first<INF; i++) cerr<<"{"<<X[i].first<<", ("<<X[i].second.first<<", "<<X[i].second.second<<")}  ";
	cerr<<"\n";
}
void Build(int id, int tl, int tr){
	if (tr-tl==1){
		seg[id]=F[X[tl]][X[tr]];
		return ;
	}
	int mid=(tl+tr)>>1;
	Build(id<<1, tl, mid);
	Build(id<<1 | 1, mid, tr);
	seg[id]=Merge(seg[id<<1], seg[id<<1 | 1]);
}
void Set(int id, int tl, int tr, int pos){
	if (pos<tl || tr<=pos) return ;
	if (tr-tl==1){
		seg[id]=F[X[tl]][X[tr]];
		return ;
	}
	int mid=(tl+tr)>>1;
	Set(id<<1, tl, mid, pos);
	Set(id<<1 | 1, mid, tr, pos);
	seg[id]=Merge(seg[id<<1], seg[id<<1 | 1]);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>T>>L;
	m<<=1;
//	assert(T==1); // 62 points
	for (int i=0; i<m; ){
		cin>>u>>v>>x;
		U[i]=u, V[i]=v, W[i]=x, G[u].pb(i++);
		U[i]=v, V[i]=u, W[i]=x, G[v].pb(i++);
	}
	memset(dist, 63, sizeof(dist));
	for (int i=0; i<m; i++){
		pq.push({dist[i][i]=0, i});
		while (pq.size()){
			int x=pq.top().second;
			pq.pop();
			if (mark[i][x]) continue ;
			mark[i][x]=1;
			for (int y:G[V[x]]) if (x^y^1 && dist[i][y]>dist[i][x]+W[y])
				pq.push({dist[i][y]=dist[i][x]+W[y], y});
		}
	}
	for (int i=0; i<5; i++) F[0][0][i]={INF, {-1, -1}};
	for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) F[i][j]=F[0][0];
	for (int u=1; u<=n; u++) for (int v=u+1; v<=n; v++){
		for (int i:G[u]) for (int j:G[v]) F[u][v][0]=min(F[u][v][0], {W[i]+dist[i][j^1], {i>>1, j>>1}});
		int a=F[u][v][0].second.first, b=F[u][v][0].second.second;
		for (int i:G[u]) for (int j:G[v]){
			if ((i>>1)!=a) F[u][v][1]=min(F[u][v][1], {W[i]+dist[i][j^1], {i>>1, j>>1}});
			if ((j>>1)!=b) F[u][v][2]=min(F[u][v][2], {W[i]+dist[i][j^1], {i>>1, j>>1}});
		}
		int c=F[u][v][1].second.first, d=F[u][v][1].second.second;
		int e=F[u][v][2].second.first, f=F[u][v][2].second.second;
		for (int i:G[u]) for (int j:G[v]){
			if ((i>>1)!=a && (j>>1)!=d) F[u][v][3]=min(F[u][v][3], {W[i]+dist[i][j^1], {i>>1, j>>1}});
			if ((i>>1)!=e && (j>>1)!=b) F[u][v][4]=min(F[u][v][4], {W[i]+dist[i][j^1], {i>>1, j>>1}});
		}
		for (int i=0; i<5; i++) F[v][u][i]={F[u][v][i].first, {F[u][v][i].second.second, F[u][v][i].second.first}};
	}
//	cerr<<"F[4][2]: ";print(F[4][2]);
//	cerr<<"F[2][4]: ";print(F[2][4]);
//	print(Merge(F[4][2], F[2][4]));
//	cerr<<"F[2][3]: ";print(F[2][3]);
	
	for (int i=1; i<=L; i++) cin>>X[i];
	Build(1, 1, L);
	while (T--){
		cin>>x>>y;
		X[x]=y;
		Set(1, 1, L, x-1);
		Set(1, 1, L, x);
		ll res=seg[1][0].first;
		if (res>=INF) res=-1;
		cout<<res<<"\n";
	}
	
	return 0;
}
/*
3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1


5 5 1 4
2 5 1
2 4 1
1 3 8
4 5 6
3 4 4
1 2 5 2
2 3

5 5 1 4
1 4 9
3 5 2
2 4 1
2 3 5
4 5 8
4 2 4 3
4 1

5 5 1 3
1 4 9
3 5 2
2 4 1
2 3 5
4 5 8
4 2 4
3 4

*/

Compilation message (stderr)

wild_boar.cpp: In function 'DATA Merge(DATA, DATA)':
wild_boar.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i=1; i<vec.size() && sz<5; i++){
      |                ~^~~~~~~~~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:124:7: warning: unused variable 'c' [-Wunused-variable]
  124 |   int c=F[u][v][1].second.first, d=F[u][v][1].second.second;
      |       ^
wild_boar.cpp:125:34: warning: unused variable 'f' [-Wunused-variable]
  125 |   int e=F[u][v][2].second.first, f=F[u][v][2].second.second;
      |                                  ^

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