Submission #1220476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220476		siewjh	Two Transportations (JOI19_transportations)	C++20	100 / 100	316 ms	48912 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    const int MAXN = 2005;
    const int inf = 1e9;
    int N, pd = 0;
    int dist[MAXN];
    bool vis[MAXN];
    vector<pair<int, int>> adj[MAXN];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    int dcnt = 0, dval = 0, xcnt = 0, xval = 0, cntid = 0;

	void clear(){
		dcnt = 0; dval = 0; xcnt = 0; xval = 0;
	}
    void send(int x, int b){
        for (int i = 0; i < b; i++) SendA(x & (1 << i));
    }
    void process(int x){
		cntid++; vis[x] = 1;
		for (auto [nn, nd] : adj[x])
			if (dist[nn] > dist[x] + nd){
				dist[nn] = dist[x] + nd;
				pq.push({dist[nn], nn});
			}
	}
	void sendd(){
		while (!pq.empty() && vis[pq.top().second]) pq.pop();
		if (pq.empty()) send(511, 9);
		else send(pq.top().first - pd, 9);
	}
	void compare(){
		if (!pq.empty() && pq.top().first <= pd + dval){
			int x = pq.top().second; pd = pq.top().first; pq.pop();
			send(x, 11);
			dist[x] = pd;
			process(x); clear();
			if (cntid < N) sendd();
		}
	}
	void oath(){
		int x = xval; pd += dval;
		dist[x] = pd;
		process(x); clear();
		if (cntid < N) sendd();
	}
}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C){
    ::N = N;
    for (int i = 0; i < A; i++){
        int u = U[i], v = V[i], c = C[i];
        adj[u].push_back({v, c}); adj[v].push_back({u, c});
    }
    for (int i = 0; i < N; i++) dist[i] = inf;
    dist[0] = 0;
	process(0);
	if (cntid < N) sendd();
}

void ReceiveA(bool x) {
	if (dcnt < 9){
        if (x) dval += (1 << dcnt);
        dcnt++;
        if (dcnt == 9) compare();
    }
    else{
        if (x) xval += (1 << xcnt);
        xcnt++;
        if (xcnt == 11) oath();
    }
}

vector<int> Answer() {
	vector<int> ans(N);
	for (int i = 0; i < N; i++) ans[i] = dist[i];
	return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    const int MAXN = 2005;
    const int inf = 1e9;
    int N, pd = 0;
    int dist[MAXN];
    bool vis[MAXN];
    vector<pair<int, int>> adj[MAXN];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    int dcnt = 0, dval = 0, xcnt = 0, xval = 0, cntid = 0;

	void clear(){
		dcnt = 0; dval = 0; xcnt = 0; xval = 0;
	}
    void send(int x, int b){
        for (int i = 0; i < b; i++) SendB(x & (1 << i));
    }
    void process(int x){
		cntid++; vis[x] = 1;
		for (auto [nn, nd] : adj[x])
			if (dist[nn] > dist[x] + nd){
				dist[nn] = dist[x] + nd;
				pq.push({dist[nn], nn});
			}
	}
	void sendd(){
		while (!pq.empty() && vis[pq.top().second]) pq.pop();
		if (pq.empty()) send(511, 9);
		else send(pq.top().first - pd, 9);
	}
	void compare(){
		if (!pq.empty() && pq.top().first < pd + dval){
			int x = pq.top().second; pd = pq.top().first; pq.pop();
			send(x, 11);
			dist[x] = pd;
			process(x); clear();
			if (cntid < N) sendd();
		}
	}
	void oath(){
		int x = xval; pd += dval;
		dist[x] = pd;
		process(x); clear();
		if (cntid < N) sendd();
	}
}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
	::N = N;
	for (int i = 0; i < B; i++){
		int u = S[i], v = T[i], c = D[i];
		adj[u].push_back({v, c}); adj[v].push_back({u, c});
	}
	for (int i = 0; i < N; i++) dist[i] = inf;
	dist[0] = 0;
	process(0);
	if (cntid < N) sendd();
}

void ReceiveB(bool y) {
    if (dcnt < 9){
        if (y) dval += (1 << dcnt);
        dcnt++;
        if (dcnt == 9) compare();
    }
    else{
        if (y) xval += (1 << xcnt);
        xcnt++;
        if (xcnt == 11) oath();
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16