oj.uz

Submission #768151

# Submission time Handle Problem Language Result Execution time Memory
768151 2023-06-27T15:21:02 Z marvinthang Two Transportations (JOI19_transportations) C++17
52 / 100
 458 ms 43552 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, last, 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;
		last = dist[u];
		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;
		int x = min(dist[u] - last, 500);
		REP(i, 9) SendA(BIT(x, 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 < 9) {
		if (x) pdv |= MASK(cnt);
		if (++cnt == 9) {
			pdv += last;
			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 - 9);
		if (++cnt == 20) {
			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, last, 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;
		last = dist[u];
		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;
		int x = min(dist[u] - last, 500);
		REP(i, 9) SendB(BIT(x, 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 < 9) {
		if (x) pdv |= MASK(cnt);
		if (++cnt == 9) {
			pdv += last;
			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 - 9);
		if (++cnt == 20) {
			minimize(dist[pv], pdv);
			dijkstra(pv);
			send_min();
			cnt = 0;
			pdv = 0;
		}
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 668 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Incorrect 41 ms 784 KB Output isn't correct
4 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 Incorrect 181 ms 744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 728 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Incorrect 77 ms 796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 676 KB Output is correct
2 Correct 188 ms 620 KB Output is correct
3 Correct 307 ms 13324 KB Output is correct
4 Correct 113 ms 680 KB Output is correct
5 Correct 227 ms 9900 KB Output is correct
6 Correct 195 ms 656 KB Output is correct
7 Correct 212 ms 656 KB Output is correct
8 Correct 162 ms 656 KB Output is correct
9 Correct 281 ms 18036 KB Output is correct
10 Correct 275 ms 18140 KB Output is correct
11 Correct 298 ms 35420 KB Output is correct
12 Correct 307 ms 30700 KB Output is correct
13 Correct 198 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 178 ms 676 KB Output is correct
2 Correct 188 ms 620 KB Output is correct
3 Correct 307 ms 13324 KB Output is correct
4 Correct 113 ms 680 KB Output is correct
5 Correct 227 ms 9900 KB Output is correct
6 Correct 195 ms 656 KB Output is correct
7 Correct 212 ms 656 KB Output is correct
8 Correct 162 ms 656 KB Output is correct
9 Correct 281 ms 18036 KB Output is correct
10 Correct 275 ms 18140 KB Output is correct
11 Correct 298 ms 35420 KB Output is correct
12 Correct 307 ms 30700 KB Output is correct
13 Correct 198 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 170 ms 668 KB Output is correct
16 Correct 247 ms 528 KB Output is correct
17 Correct 261 ms 528 KB Output is correct
18 Correct 272 ms 10008 KB Output is correct
19 Correct 224 ms 656 KB Output is correct
20 Correct 216 ms 10184 KB Output is correct
21 Correct 238 ms 704 KB Output is correct
22 Correct 239 ms 656 KB Output is correct
23 Correct 341 ms 21984 KB Output is correct
24 Correct 268 ms 22064 KB Output is correct
25 Correct 447 ms 43552 KB Output is correct
26 Correct 389 ms 36512 KB Output is correct
27 Correct 255 ms 656 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 676 KB Output is correct
2 Correct 188 ms 620 KB Output is correct
3 Correct 307 ms 13324 KB Output is correct
4 Correct 113 ms 680 KB Output is correct
5 Correct 227 ms 9900 KB Output is correct
6 Correct 195 ms 656 KB Output is correct
7 Correct 212 ms 656 KB Output is correct
8 Correct 162 ms 656 KB Output is correct
9 Correct 281 ms 18036 KB Output is correct
10 Correct 275 ms 18140 KB Output is correct
11 Correct 298 ms 35420 KB Output is correct
12 Correct 307 ms 30700 KB Output is correct
13 Correct 198 ms 656 KB Output is correct
14 Correct 0 ms 400 KB Output is correct
15 Correct 170 ms 668 KB Output is correct
16 Correct 247 ms 528 KB Output is correct
17 Correct 261 ms 528 KB Output is correct
18 Correct 272 ms 10008 KB Output is correct
19 Correct 224 ms 656 KB Output is correct
20 Correct 216 ms 10184 KB Output is correct
21 Correct 238 ms 704 KB Output is correct
22 Correct 239 ms 656 KB Output is correct
23 Correct 341 ms 21984 KB Output is correct
24 Correct 268 ms 22064 KB Output is correct
25 Correct 447 ms 43552 KB Output is correct
26 Correct 389 ms 36512 KB Output is correct
27 Correct 255 ms 656 KB Output is correct
28 Correct 289 ms 656 KB Output is correct
29 Correct 382 ms 640 KB Output is correct
30 Correct 458 ms 23984 KB Output is correct
31 Incorrect 7 ms 660 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 668 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Incorrect 41 ms 784 KB Output isn't correct
4 Halted 0 ms 0 KB -