oj.uz

Submission #524484

# Submission time Handle Problem Language Result Execution time Memory
524484 2022-02-09T09:31:40 Z fatemetmhr Wild Boar (JOI18_wild_boar) C++17
0 / 100
 1 ms 460 KB 
//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;


ll h1[maxn5], h2[maxn5];
pair <ll, ll> dis[maxn5][2][maxn5];
int root[maxn5][2][maxn5];
int pa[maxn5];
set <pair<ll, pair<int, int>>> av;
vector <pair<int, int>> adj[maxn5];
int a[maxn5], b[maxn5];
ll c[maxn5];
int x[maxn];
pair <ll, ll> done[maxn];
int mxx[maxn];
int n;

inline void dij(int e, bool ty){
	for(int i = 0; i < n; i++){
		h1[i] = h2[i] = inf;
	}
	memset(pa, -1, sizeof pa);
	
	int uu = a[e], vu = b[e];
	if(ty){
		uu = b[e];
		vu = a[e];
	}
	
	h1[vu] = 0;
	pa[vu] = e;

	av.clear();
	
	for(int i = 0; i < n; i++){
		av.insert({h1[i], {i, 0}});
		av.insert({h2[i], {i, 1}});
	}
	
	while(!av.empty()){
		int  v = av.begin() -> se.fi, ty = av.begin() -> se.se;
		av.erase(av.begin());
		if(ty == 0){
			if(h1[v] >= inf)
				continue;
			for(auto p : adj[v]) if(p.se != pa[v] && (v != uu || p.fi != vu)){
				int u = p.fi;
				ll val = h1[v] + c[p.se];
				if(val <= h1[u]){
					av.erase({h1[u], {u, 0}});
					av.erase({h2[u], {u, 1}});
					h2[u] = h1[u];
					h1[u] = val;
					pa[u] = p.se;
					av.insert({h1[u], {u, 0}});
					av.insert({h2[u], {u, 1}});
				}
				else if(val < h2[u]){
					av.erase({h2[u], {u, 1}});
					h2[u] = val;
					av.insert({h2[u], {u, 1}});
				}
			}
		}
		else{
			if(h2[v] >= inf)
				continue;
			int i = pa[v];
			int u = a[i] == v ? b[i] : a[i];
			if(v != uu || u != vu){
				ll val = h1[v] + c[i];
				if(val <= h1[u]){
					av.erase({h1[u], {u, 0}});
					av.erase({h2[u], {u, 1}});
					h2[u] = h1[u];
					h1[u] = val;
					pa[u] = i;
					av.insert({h1[u], {u, 0}});
					av.insert({h2[u], {u, 1}});
				}
				else if(val < h2[u]){
					av.erase({h2[u], {u, 1}});
					h2[u] = val;
					av.insert({h2[u], {u, 1}});
				}
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		dis[e][ty][i] = {h1[i], h2[i]};
		root[e][ty][i] = pa[i];
	}
	
}

inline bool get_ty(int e, int u, int v){
	return a[e] == v;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int m, t, l; cin >> n >> m >> t >> l;
	for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
		adj[a[i]].pb({b[i], i});
		adj[b[i]].pb({a[i], i});
	}
	
	for(int i = 0; i < m; i++){
		dij(i, 0);
		dij(i, 1);
	}

	for(int i = 0; i < l; i++){
		cin >> x[i];
		x[i]--;
	}
	int a, b; cin >> a >> b;
	a--; b--;
	x[a] = b;
	
	

	for(int i = 0; i < l; i++){
		if(i == 0){
			done[0] = {0, 0};
			mxx[0] = adj[x[0]][0].se;
		}
		else{
			int u = x[i - 1], v = x[i];
			done[i].fi = inf;
			int opt = mxx[i - 1];
			for(auto p : adj[u]){
				int z = p.fi, id = p.se;
				ll val, val2;
				if(id != mxx[i - 1]){
					val = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].fi + c[id];
					val2 = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].se + c[id];
				}
				else{
					val = done[i - 1].se + dis[id][get_ty(id, u, z)][v].fi + c[id];
					val2 = done[i - 1].se + dis[id][get_ty(id, u, z)][v].se + c[id];
				}
				if(val <= done[i].fi){
					opt = id;
					done[i].fi = val;
					done[i].se = val2;
					mxx[i] = root[id][get_ty(id, u, z)][v];
				}
			
			}
			
			for(auto p : adj[u]){
				int z = p.fi, id = p.se;
				ll val;
				if(id != mxx[i - 1]){
					val = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].fi + c[id];
				}
				else{
					val = done[i - 1].se + dis[id][get_ty(id, u, z)][v].fi + c[id];
				}
				if(val <= done[i].se && root[id][get_ty(id, u, z)][v] != mxx[i]){
					done[i].se = val;
				}
			
			}
		}
		//cout << i << ' ' << x[i] << ' ' << done[i].fi << ' ' << done[i].se << endl;
	}
	
	cout << (done[l - 1].fi == inf ? -1 : done[l - 1].fi) << endl;
	
	
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:156:8: warning: variable 'opt' set but not used [-Wunused-but-set-variable]
  156 |    int opt = mxx[i - 1];
      |        ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -