oj.uz

Submission #768141

# Submission time Handle Problem Language Result Execution time Memory
768141 2023-06-27T14:22:32 Z marvinthang Two Transportations (JOI19_transportations) C++17
38 / 100
 690 ms 35416 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 = 1e9;

	int N, cnt, pu, pdu;
	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(void) {
		int u = find_min();
		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;
		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 = pu = pdu = 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();
	send_min();
}

void ReceiveA(bool x) {
	if (x) {
		if (cnt < 11) pu |= MASK(cnt);
		else pdu |= MASK(cnt - 11);
	}
	if (++cnt == 31) {
		minimize(dist[pu], pdu);
		dijkstra();
		send_min();
		cnt = 0;
		pu = 0;
		pdu = 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 = 1e9;

	int N, cnt, pu, pdu;
	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(void) {
		int u = find_min();
		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;
		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 = pu = pdu = 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();
	send_min();
}

void ReceiveB(bool y) {
	if (y) {
		if (cnt < 11) pu |= MASK(cnt);
		else pdu |= MASK(cnt - 11);
	}
	if (++cnt == 31) {
		minimize(dist[pu], pdu);
		dijkstra();
		send_min();
		cnt = 0;
		pu = 0;
		pdu = 0;
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 214 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 0 ms 400 KB Output is correct
2 Runtime error 223 ms 432 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 656 KB Output is correct
2 Correct 277 ms 680 KB Output is correct
3 Correct 353 ms 13252 KB Output is correct
4 Correct 378 ms 656 KB Output is correct
5 Correct 459 ms 9972 KB Output is correct
6 Correct 443 ms 656 KB Output is correct
7 Correct 344 ms 688 KB Output is correct
8 Correct 417 ms 696 KB Output is correct
9 Correct 538 ms 18104 KB Output is correct
10 Correct 502 ms 18128 KB Output is correct
11 Correct 690 ms 35416 KB Output is correct
12 Correct 414 ms 30780 KB Output is correct
13 Correct 361 ms 600 KB Output is correct
14 Correct 0 ms 400 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 656 KB Output is correct
2 Correct 277 ms 680 KB Output is correct
3 Correct 353 ms 13252 KB Output is correct
4 Correct 378 ms 656 KB Output is correct
5 Correct 459 ms 9972 KB Output is correct
6 Correct 443 ms 656 KB Output is correct
7 Correct 344 ms 688 KB Output is correct
8 Correct 417 ms 696 KB Output is correct
9 Correct 538 ms 18104 KB Output is correct
10 Correct 502 ms 18128 KB Output is correct
11 Correct 690 ms 35416 KB Output is correct
12 Correct 414 ms 30780 KB Output is correct
13 Correct 361 ms 600 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Runtime error 170 ms 348 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 656 KB Output is correct
2 Correct 277 ms 680 KB Output is correct
3 Correct 353 ms 13252 KB Output is correct
4 Correct 378 ms 656 KB Output is correct
5 Correct 459 ms 9972 KB Output is correct
6 Correct 443 ms 656 KB Output is correct
7 Correct 344 ms 688 KB Output is correct
8 Correct 417 ms 696 KB Output is correct
9 Correct 538 ms 18104 KB Output is correct
10 Correct 502 ms 18128 KB Output is correct
11 Correct 690 ms 35416 KB Output is correct
12 Correct 414 ms 30780 KB Output is correct
13 Correct 361 ms 600 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Runtime error 170 ms 348 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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