oj.uz

Submission #726183

# Submission time Handle Problem Language Result Execution time Memory
726183 2023-04-18T16:25:32 Z GusterGoose27 Wild Boar (JOI18_wild_boar) C++17
12 / 100
 691 ms 862276 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, bool> plb;
typedef pair<ll, int> pli;

const int MAXN = 100;
const int MAX_PATH = 1e5;
const ll inf = 1e15;
int n, m, t, l;

class path {
public:
	ll len;
	int s, e;
	path(ll l, int s, int e) : len(l), s(s), e(e) {}
	path() {}
};

int hsh(int i, int j) {
	return n*i+j; // j is prev node, i is cur node
}

vector<pii> edges[MAXN];
vector<pii> edges2[MAXN*MAXN];
ll dist[MAXN*MAXN][MAXN*MAXN];
int seq[MAX_PATH];

void dijkstra(int s) {
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	fill(dist[s], dist[s]+n*n, inf);
	dist[s][s] = 0;
	pq.push(pli(0, s));
	while (!pq.empty()) {
		pii tp = pq.top();
		pq.pop();
		if (dist[s][tp.second] < tp.first) continue;
		for (pii e: edges2[tp.second]) {
			ll ndist = tp.first+e.second;
			if (ndist < dist[s][e.first]) {
				dist[s][e.first] = ndist;
				pq.push(pli(ndist, e.first));
			}
		}
	}
}

ll dp[MAX_PATH][MAXN];

ll make_dp() {
	fill(dp[l-1], dp[l-1]+n, 0);
	for (int i = l-2; i > 0; i--) {
		for (pii j: edges[seq[i]]) {
			dp[i][j.first] = inf;
			for (pii k: edges[seq[i+1]]) {
				dp[i][j.first] = min(dp[i][j.first], dp[i+1][k.first]+dist[hsh(seq[i],j.first)][hsh(seq[i+1], k.first)]);
			}
		}
	}
	ll ans = inf;
	for (pii i: edges[seq[0]]) 
		for (pii j: edges[seq[1]]) ans = min(ans, dp[1][j.first]+i.second+dist[hsh(i.first, seq[0])][hsh(seq[1], j.first)]);
	if (ans == inf) return -1;
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> t >> l;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c; a--; b--;
		edges[a].push_back(pii(b, c));
		edges[b].push_back(pii(a, c));
	}
	for (int i = 0; i < n; i++) {
		for (pii j: edges[i]) {
			for (pii k: edges[i]) {
				if (k.first == j.first) continue;
				edges2[hsh(i, j.first)].push_back(pii(hsh(k.first, i), k.second));
			}
		}
	}
	for (int i = 0; i < n*n; i++) {
		dijkstra(i);
	}
	for (int i = 0; i < l; i++) {
		cin >> seq[i]; seq[i]--;
	}
	for (int i = 0; i < t; i++) {
		int p, v; cin >> p >> v;
		p--; v--;
		seq[p] = v;
		cout << make_dp() << "\n";
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 744 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 832 KB Output is correct
13 Correct 1 ms 828 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 956 KB Output is correct
19 Correct 2 ms 1088 KB Output is correct
20 Correct 3 ms 988 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 744 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 832 KB Output is correct
13 Correct 1 ms 828 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 956 KB Output is correct
19 Correct 2 ms 1088 KB Output is correct
20 Correct 3 ms 988 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 3548 KB Output is correct
27 Correct 691 ms 862276 KB Output is correct
28 Incorrect 475 ms 862212 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 744 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 832 KB Output is correct
13 Correct 1 ms 828 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 956 KB Output is correct
19 Correct 2 ms 1088 KB Output is correct
20 Correct 3 ms 988 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 3548 KB Output is correct
27 Correct 691 ms 862276 KB Output is correct
28 Incorrect 475 ms 862212 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 700 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 744 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 832 KB Output is correct
13 Correct 1 ms 828 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 3 ms 860 KB Output is correct
18 Correct 2 ms 956 KB Output is correct
19 Correct 2 ms 1088 KB Output is correct
20 Correct 3 ms 988 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 3548 KB Output is correct
27 Correct 691 ms 862276 KB Output is correct
28 Incorrect 475 ms 862212 KB Output isn't correct
29 Halted 0 ms 0 KB -