oj.uz

Submission #798381

# Submission time Handle Problem Language Result Execution time Memory
798381 2023-07-30T16:23:45 Z hugo_pm Wild Boar (JOI18_wild_boar) C++17
47 / 100
 18000 ms 183116 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAX_N = 2005, MAX_ARRET = 1e5+5;
int nbNode, nbEdge, nbReq, nbArret;
vector<int> adj[MAX_N];
int xorNode[MAX_N];
int poids[MAX_N];
int arrets[MAX_ARRET];

struct Chemin {
	int len, fst, lst;
	bool operator<(const Chemin &oth) const {
		return tie(len, fst, lst) < tie(oth.len, oth.fst, oth.lst);
	}
	bool operator==(const Chemin &oth) const {
		return tie(len, fst, lst) == tie(oth.len, oth.fst, oth.lst);
	}
};

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

string to_string(const Chemin c) {
	return "(len=" + to_string(c.len) + ", fst=" + to_string(c.fst) + ", lst=" + to_string(c.lst) + ")";
}

int repondre() {
	vector<vector<vector<Chemin>>> matrice(nbNode);
	auto compressTab = [&](vector<Chemin> &chemins) {
		sort(all(chemins));
		map<int, int> cntFirst, cntLast;
		set<pair<int, int>> vus;
		vector<Chemin> ret;
		for (Chemin chem : chemins) {
			if (ret.size() > 8)
				break;
			if (cntFirst[chem.fst] == 3 or cntLast[chem.lst] == 3 or vus.count({chem.fst, chem.lst}))
				continue;
			ret.push_back(chem);
			cntFirst[chem.fst]++;
			cntLast[chem.lst]++;
			vus.emplace(chem.fst, chem.lst); 
		}
		return ret;
	};
	auto interesting = [&] (const Chemin &add, vector<Chemin> &V) {
		V.push_back(add);
		V = compressTab(V);
		return (find(all(V), add) != end(V));
	};
	rep(depart, 0, nbNode) {
		auto& cand = matrice[depart];
		cand.resize(nbNode);
		cand[depart].push_back({0, -1, -1});
		minpq<pair<Chemin, int>> pq;
		pq.push({cand[depart].back(), depart});
		while (!pq.empty()) {
			auto [oldChemin, node] = pq.top();
			pq.pop();
			// oldChemin.len == dist[node]
			dbg(depart, node);
			if (!interesting(oldChemin, cand[node])) {
				continue;
			}
			for (int iEdge : adj[node]) {
				if (iEdge == oldChemin.lst) continue;
				int voisin = xorNode[iEdge]^node;
				Chemin nouvChemin {
					oldChemin.len + poids[iEdge],
					(oldChemin.fst == -1 ? iEdge : oldChemin.fst),
					iEdge
				};
				if (interesting(nouvChemin, cand[voisin])) {
					dbg(voisin, cand[voisin], nouvChemin);
					pq.push({nouvChemin, voisin});
				}
			}
		}
		rep(node, 0, nbNode) {
			assert(sz(cand[node]) <= 9);
		}
	}
	vector<Chemin> candidats;
	candidats.push_back({0, -1, -1});
	rep(iRawArret, 1, nbArret) {
		int prev = arrets[iRawArret-1];
		int cur = arrets[iRawArret];
		dbg(prev+1, cur+1);
		dbg(matrice[prev][cur]);
		vector<Chemin> nv;
		for (Chemin c1 : candidats) for (Chemin c2 : matrice[prev][cur]) {
			if (c1.lst != c2.fst) {
				int newFst = (c1.fst == -1 ? c2.fst : c1.fst);
				nv.push_back({c1.len + c2.len, newFst, c2.lst});
			}
		}
		candidats = compressTab(nv);
		assert(sz(candidats) <= 9);
		dbg(candidats);
	}
	if (candidats.empty()) return -1;
	return min_element(all(candidats))->len;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> nbNode >> nbEdge >> nbReq >> nbArret;
	rep(iEdge, 0, nbEdge) {
		int u, v; cin >> u >> v;
		--u, --v;
		cin >> poids[iEdge];
		xorNode[iEdge] = u^v;
		adj[u].push_back(iEdge);
		adj[v].push_back(iEdge);
	}
	rep(iArret, 0, nbArret) {
		cin >> arrets[iArret];
		--arrets[iArret];
	}
	rep(iReq, 0, nbReq) {
		int indice, val;
		cin >> indice >> val;
		--indice, --val;
		arrets[indice] = val;
		cout << repondre() << '\n';
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 376 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 372 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 368 KB Output is correct
25 Correct 1 ms 340 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 376 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 372 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 368 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 14 ms 468 KB Output is correct
27 Correct 15 ms 2136 KB Output is correct
28 Correct 13 ms 2004 KB Output is correct
29 Correct 1006 ms 5712 KB Output is correct
30 Correct 927 ms 5248 KB Output is correct
31 Correct 795 ms 5472 KB Output is correct
32 Correct 796 ms 5572 KB Output is correct
33 Correct 1081 ms 9564 KB Output is correct
34 Correct 1097 ms 9788 KB Output is correct
35 Correct 839 ms 8884 KB Output is correct
36 Correct 838 ms 8316 KB Output is correct
37 Correct 1145 ms 10148 KB Output is correct
38 Correct 935 ms 12748 KB Output is correct
39 Correct 775 ms 10436 KB Output is correct
40 Correct 866 ms 12996 KB Output is correct
41 Correct 862 ms 12864 KB Output is correct
42 Correct 709 ms 12004 KB Output is correct
43 Correct 648 ms 14504 KB Output is correct
44 Correct 645 ms 14296 KB Output is correct
45 Correct 141 ms 9308 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 376 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 372 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 368 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 14 ms 468 KB Output is correct
27 Correct 15 ms 2136 KB Output is correct
28 Correct 13 ms 2004 KB Output is correct
29 Correct 1006 ms 5712 KB Output is correct
30 Correct 927 ms 5248 KB Output is correct
31 Correct 795 ms 5472 KB Output is correct
32 Correct 796 ms 5572 KB Output is correct
33 Correct 1081 ms 9564 KB Output is correct
34 Correct 1097 ms 9788 KB Output is correct
35 Correct 839 ms 8884 KB Output is correct
36 Correct 838 ms 8316 KB Output is correct
37 Correct 1145 ms 10148 KB Output is correct
38 Correct 935 ms 12748 KB Output is correct
39 Correct 775 ms 10436 KB Output is correct
40 Correct 866 ms 12996 KB Output is correct
41 Correct 862 ms 12864 KB Output is correct
42 Correct 709 ms 12004 KB Output is correct
43 Correct 648 ms 14504 KB Output is correct
44 Correct 645 ms 14296 KB Output is correct
45 Correct 141 ms 9308 KB Output is correct
46 Correct 2049 ms 15600 KB Output is correct
47 Correct 17220 ms 102624 KB Output is correct
48 Execution timed out 18038 ms 183116 KB Time limit exceeded
49 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 376 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 372 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 368 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 14 ms 468 KB Output is correct
27 Correct 15 ms 2136 KB Output is correct
28 Correct 13 ms 2004 KB Output is correct
29 Correct 1006 ms 5712 KB Output is correct
30 Correct 927 ms 5248 KB Output is correct
31 Correct 795 ms 5472 KB Output is correct
32 Correct 796 ms 5572 KB Output is correct
33 Correct 1081 ms 9564 KB Output is correct
34 Correct 1097 ms 9788 KB Output is correct
35 Correct 839 ms 8884 KB Output is correct
36 Correct 838 ms 8316 KB Output is correct
37 Correct 1145 ms 10148 KB Output is correct
38 Correct 935 ms 12748 KB Output is correct
39 Correct 775 ms 10436 KB Output is correct
40 Correct 866 ms 12996 KB Output is correct
41 Correct 862 ms 12864 KB Output is correct
42 Correct 709 ms 12004 KB Output is correct
43 Correct 648 ms 14504 KB Output is correct
44 Correct 645 ms 14296 KB Output is correct
45 Correct 141 ms 9308 KB Output is correct
46 Correct 2049 ms 15600 KB Output is correct
47 Correct 17220 ms 102624 KB Output is correct
48 Execution timed out 18038 ms 183116 KB Time limit exceeded
49 Halted 0 ms 0 KB -