oj.uz

Submission #670492

# Submission time Handle Problem Language Result Execution time Memory
670492 2022-12-09T09:27:39 Z ymm Two Transportations (JOI19_transportations) C++17
6 / 100
 3000 ms 27872 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();
}

int get_nxt()
{
	return s.size()? s.begin()->first: 511 + lst_d;
}

void cmp()
{
	int self = get_nxt();
	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();
	cerr << "A with " << v << " dis " << d << '\n';
	s.erase(s.begin());
	for (auto [u, w] : A[v])
		up(u, d+w);
	lst_d = d;
	--rem;
	if (!rem)
		return;
	send(get_nxt() - 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();
}

int get_nxt()
{
	return s.size()? s.begin()->first: 511 + lst_d;
}

void cmp()
{
	int self = get_nxt();
	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();
	cerr << "B with " << v << " dis " << d << '\n';
	s.erase(s.begin());
	for (auto [u, w] : A[v])
		up(u, d+w);
	lst_d = d;
	--rem;
	if (!rem)
		return;
	send(get_nxt() - 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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 996 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 567 ms 1248 KB Output is correct
4 Correct 689 ms 10336 KB Output is correct
5 Correct 35 ms 960 KB Output is correct
6 Correct 627 ms 2588 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 656 KB Output is correct
2 Correct 524 ms 1080 KB Output is correct
3 Correct 625 ms 1212 KB Output is correct
4 Correct 773 ms 27872 KB Output is correct
5 Correct 649 ms 24292 KB Output is correct
6 Correct 107 ms 736 KB Output is correct
7 Incorrect 750 ms 24500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 396 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 396 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 396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 996 KB Output is correct
2 Correct 0 ms 656 KB Output is correct
3 Correct 567 ms 1248 KB Output is correct
4 Correct 689 ms 10336 KB Output is correct
5 Correct 35 ms 960 KB Output is correct
6 Correct 627 ms 2588 KB Output is correct
7 Correct 0 ms 656 KB Output is correct
8 Correct 524 ms 1080 KB Output is correct
9 Correct 625 ms 1212 KB Output is correct
10 Correct 773 ms 27872 KB Output is correct
11 Correct 649 ms 24292 KB Output is correct
12 Correct 107 ms 736 KB Output is correct
13 Incorrect 750 ms 24500 KB Output isn't correct
14 Halted 0 ms 0 KB -