oj.uz

Submission #670488

# Submission time Handle Problem Language Result Execution time Memory
670488 2022-12-09T09:11:10 Z ymm Two Transportations (JOI19_transportations) C++17
0 / 100
 3000 ms 712 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace {

const int N = 2048;
const int inf = 1e9;
vector<pii> A[N];
int dis[N];
set<pii> s;
int rem;
int n;

int want;
void (*want_func)();
queue<bool> q;
int lst_d;
int recv_up_d;

}  // namespace

namespace {

void send(int x, int b)
{
	cerr << "A send " << x << '\n';
	while (b--) {
		SendA(x & 1);
		x /= 2;
	}
}

int recv(int b)
{
	int ans = 0;
	Loop (i,0,b) {
		ans ^= (int)q.front() << i;
		q.pop();
	}
	cerr << "A recv " << ans << '\n';
	return ans;
}

void up(int v, int d)
{
	if (d >= dis[v])
		return;
	s.erase({dis[v], v});
	dis[v] = d;
	s.insert({dis[v], v});
}

void recv_up();
void cmp();
void dij();

void recv_up()
{
	int v = recv(11);
	up(v, recv_up_d);
	dij();
}

void cmp()
{
	int self = s.begin()->first;
	int other = recv(9) + lst_d;
	if (self > other) {
		want = 11;
		want_func = recv_up;
		recv_up_d = other;
	} else {
		send(s.begin()->second, 11);
		dij();
	}
}

void dij()
{
	auto [d, v] = *s.begin();
	s.erase(s.begin());
	for (auto [u, w] : A[v])
		up(u, d+w);
	lst_d = dis[v];
	--rem;
	if (!rem)
		return;
	int u = s.begin()->second;
	send(dis[u] - lst_d, 9);
	want = 9;
	want_func = cmp;
}

}

void InitA(int _n, int m, std::vector<int> V, std::vector<int> U,
           std::vector<int> W)
{
	n = _n;
	rem = n;
	Loop (i,0,m) {
		int v = V[i], u = U[i], w = W[i];
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	fill(dis, dis+n, inf);
	up(0, 0);
	dij();
}

void ReceiveA(bool x)
{
	q.push(x);
	--want;
	if (!want) {
		want_func();
	}
}

std::vector<int> Answer()
{
	vector<int> ans(n);
	Loop (i,0,n)
		ans[i] = dis[i];
	return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace {

const int N = 2048;
const int inf = 1e9;
vector<pii> A[N];
int dis[N];
set<pii> s;
int rem;
int n;

int want;
void (*want_func)();
queue<bool> q;
int lst_d;
int recv_up_d;

}  // namespace

namespace {

void send(int x, int b)
{
	cerr << "B send " << x << '\n';
	while (b--) {
		SendB(x & 1);
		x /= 2;
	}
}

int recv(int b)
{
	int ans = 0;
	Loop (i,0,b) {
		ans ^= (int)q.front() << i;
		q.pop();
	}
	cerr << "B recv " << ans << '\n';
	return ans;
}

void up(int v, int d)
{
	if (d >= dis[v])
		return;
	s.erase({dis[v], v});
	dis[v] = d;
	s.insert({dis[v], v});
}

void recv_up();
void cmp();
void dij();

void recv_up()
{
	int v = recv(11);
	up(v, recv_up_d);
	dij();
}

void cmp()
{
	int self = s.begin()->first;
	int other = recv(9) + lst_d;
	if (self >= other) {
		want = 11;
		want_func = recv_up;
		recv_up_d = other;
	} else {
		send(s.begin()->second, 11);
		dij();
	}
}

void dij()
{
	auto [d, v] = *s.begin();
	s.erase(s.begin());
	for (auto [u, w] : A[v])
		up(u, d+w);
	lst_d = dis[v];
	--rem;
	if (!rem)
		return;
	int u = s.begin()->second;
	send(dis[u] - lst_d, 9);
	want = 9;
	want_func = cmp;
}

}

void InitB(int _n, int m, std::vector<int> V, std::vector<int> U,
           std::vector<int> W)
{
	n = _n;
	rem = n;
	Loop (i,0,m) {
		int v = V[i], u = U[i], w = W[i];
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	fill(dis, dis+n, inf);
	up(0, 0);
	dij();
}

void ReceiveB(bool x)
{
	q.push(x);
	--want;
	if (!want) {
		want_func();
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 712 KB Output is correct
2 Execution timed out 3000 ms 328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 328 KB Time limit exceeded
2 Halted 0 ms 0 KB -