oj.uz

Submission #768148

# Submission time Handle Problem Language Result Execution time Memory
768148 2023-06-27T15:11:39 Z marvinthang Two Transportations (JOI19_transportations) C++17
52 / 100
 635 ms 43532 KB 
/*************************************
*    author: marvinthang             *
*    created: 27.06.2023 19:27:42    *
*************************************/

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
		#include "debug.h"
#else
		#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
		#define DB(...) 23
		#define db(...) 23
		#define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

namespace {

	const int INF = MASK(20) - 1;

	int N, cnt, pu, pv, pdv;
	vector <bool> used;
	vector <int> dist;
	vector <vector <pair <int, int>>> adj;

	int find_min(void) {
		int u = -1;
		REP(i, N) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
		return u;
	}

	void dijkstra(int u) {
		used[u] = true;
		for (auto [w, v]: adj[u]) minimize(dist[v], dist[u] + w);
	}

	void send_min(void) {
		int u = find_min();
		if (u == -1) return;
		pu = u;
		// REP(i, 11) SendA(BIT(u, i));
		REP(i, 20) SendA(BIT(dist[u], i));
	}

}  // namespace


void InitA(int N, int A, vector <int> U, vector <int> V, vector <int> C) {
	::N = N;
	cnt = pv = pdv = 0;
	used.resize(N);
	dist.assign(N, INF);
	adj.resize(N);
	REP(i, A) {
		adj[U[i]].emplace_back(C[i], V[i]);
		adj[V[i]].emplace_back(C[i], U[i]);
	}
	dist[0] = 0;
	dijkstra(0);
	send_min();
}

void ReceiveA(bool x) {
	if (cnt < 20) {
		if (x) pdv |= MASK(cnt);
		if (++cnt == 20) {
			if (dist[pu] <= pdv) {
				REP(i, 11) SendA(BIT(pu, i));
				dijkstra(pu);
				send_min();
				cnt = 0;
				pdv = 0;
			} else pv = 0;
		}
	} else {
		if (x) pv |= MASK(cnt - 20);
		if (++cnt == 31) {
			minimize(dist[pv], pdv);
			dijkstra(pv);
			send_min();
			cnt = 0;
			pdv = 0;
		}
	}
}

vector <int> Answer() {
	return dist;
}

/*************************************
*    author: marvinthang             *
*    created: 27.06.2023 19:28:31    *
*************************************/

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

namespace {

	const int INF = MASK(20) - 1;

	int N, cnt, pu, pv, pdv;
	vector <bool> used;
	vector <int> dist;
	vector <vector <pair <int, int>>> adj;

	int find_min(void) {
		int u = -1;
		REP(i, N) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
		return u;
	}

	void dijkstra(int u) {
		used[u] = true;
		for (auto [w, v]: adj[u]) minimize(dist[v], dist[u] + w);
	}

	void send_min(void) {
		int u = find_min();
		if (u == -1) return;
		pu = u;
		// REP(i, 11) SendB(BIT(u, i));
		REP(i, 20) SendB(BIT(dist[u], i));
	}

}  // namespace

void InitB(int N, int B, vector <int> S, vector <int> T, vector <int> D) {
	::N = N;
	cnt = pv = pdv = 0;
	used.resize(N);
	dist.assign(N, INF);
	adj.resize(N);
	REP(i, B) {
		adj[S[i]].emplace_back(D[i], T[i]);
		adj[T[i]].emplace_back(D[i], S[i]);
	}
	dist[0] = 0;
	dijkstra(0);
	send_min();
}

void ReceiveB(bool x) {
	if (cnt < 20) {
		if (x) pdv |= MASK(cnt);
		if (++cnt == 20) {
			if (dist[pu] < pdv) {
				REP(i, 11) SendB(BIT(pu, i));
				dijkstra(pu);
				send_min();
				cnt = 0;
				pdv = 0;
			} else pv = 0;
		}
	} else {
		if (x) pv |= MASK(cnt - 20);
		if (++cnt == 31) {
			minimize(dist[pv], pdv);
			dijkstra(pv);
			send_min();
			cnt = 0;
			pdv = 0;
		}
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 248 ms 332 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 400 KB Output is correct
2 Runtime error 157 ms 412 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 ms 420 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 656 KB Output is correct
2 Correct 310 ms 652 KB Output is correct
3 Correct 365 ms 13356 KB Output is correct
4 Correct 337 ms 656 KB Output is correct
5 Correct 391 ms 9896 KB Output is correct
6 Correct 349 ms 656 KB Output is correct
7 Correct 268 ms 692 KB Output is correct
8 Correct 343 ms 688 KB Output is correct
9 Correct 421 ms 18136 KB Output is correct
10 Correct 323 ms 18104 KB Output is correct
11 Correct 479 ms 35416 KB Output is correct
12 Correct 400 ms 30704 KB Output is correct
13 Correct 324 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 656 KB Output is correct
2 Correct 310 ms 652 KB Output is correct
3 Correct 365 ms 13356 KB Output is correct
4 Correct 337 ms 656 KB Output is correct
5 Correct 391 ms 9896 KB Output is correct
6 Correct 349 ms 656 KB Output is correct
7 Correct 268 ms 692 KB Output is correct
8 Correct 343 ms 688 KB Output is correct
9 Correct 421 ms 18136 KB Output is correct
10 Correct 323 ms 18104 KB Output is correct
11 Correct 479 ms 35416 KB Output is correct
12 Correct 400 ms 30704 KB Output is correct
13 Correct 324 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 420 ms 656 KB Output is correct
16 Correct 362 ms 556 KB Output is correct
17 Correct 357 ms 528 KB Output is correct
18 Correct 472 ms 10044 KB Output is correct
19 Correct 420 ms 656 KB Output is correct
20 Correct 389 ms 10216 KB Output is correct
21 Correct 458 ms 656 KB Output is correct
22 Correct 367 ms 720 KB Output is correct
23 Correct 484 ms 22084 KB Output is correct
24 Correct 584 ms 22080 KB Output is correct
25 Correct 635 ms 43532 KB Output is correct
26 Correct 508 ms 36412 KB Output is correct
27 Correct 455 ms 736 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 656 KB Output is correct
2 Correct 310 ms 652 KB Output is correct
3 Correct 365 ms 13356 KB Output is correct
4 Correct 337 ms 656 KB Output is correct
5 Correct 391 ms 9896 KB Output is correct
6 Correct 349 ms 656 KB Output is correct
7 Correct 268 ms 692 KB Output is correct
8 Correct 343 ms 688 KB Output is correct
9 Correct 421 ms 18136 KB Output is correct
10 Correct 323 ms 18104 KB Output is correct
11 Correct 479 ms 35416 KB Output is correct
12 Correct 400 ms 30704 KB Output is correct
13 Correct 324 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 420 ms 656 KB Output is correct
16 Correct 362 ms 556 KB Output is correct
17 Correct 357 ms 528 KB Output is correct
18 Correct 472 ms 10044 KB Output is correct
19 Correct 420 ms 656 KB Output is correct
20 Correct 389 ms 10216 KB Output is correct
21 Correct 458 ms 656 KB Output is correct
22 Correct 367 ms 720 KB Output is correct
23 Correct 484 ms 22084 KB Output is correct
24 Correct 584 ms 22080 KB Output is correct
25 Correct 635 ms 43532 KB Output is correct
26 Correct 508 ms 36412 KB Output is correct
27 Correct 455 ms 736 KB Output is correct
28 Runtime error 165 ms 360 KB Execution killed with signal 13
29 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 248 ms 332 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -