Submission #210704

#	Time	Username	Problem	Language	Result	Execution time	Memory
210704		erd1	Two Transportations (JOI19_transportations)	C++14	100 / 100	2262 ms	97344 KiB

Azer

#include<bits/stdc++.h>
#include "Azer.h"
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef int64_t lld;
typedef pair<int, int> pii;

namespace {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<vector<pii>> G;
    vector<int> dist;

    const int POINT = 11, WEIGHT = 9;

    int pending = 0;
    bool pendF = false; // true: POINT, false: WEIGHT
    void pend(int len){
        assert(pending == 0);
        pendF = (len == POINT);
        pending = len;
        //cerr << "Azer: pend" << endl;
    }
    void send(int x, int len){
        for(int i = len-1; i >= 0; i--)
            SendA((x>>i)&1);
        //cerr << "Azer: send " << x << endl;
    }
    int cur = 0;
    void bfs(pii p){
        assert(!dist[p.ss]);
        dist[p.ss] = p.ff;
        //cerr << "BFS" << p.ss << " " << p.ff << endl;
        for(auto i: G[p.ss]){
		    if(dist[i.ss])
			    continue;
            pq.push({i.ff+p.ff, i.ss});
        }
        while(!pq.empty() && dist[pq.top().ss])pq.pop();
        if(pq.empty())send(505, WEIGHT);
        else send(pq.top().ff-cur, WEIGHT);
        pend(WEIGHT);
    }

    void receiveWeight(int w){
        if(!pq.empty() && w + cur > pq.top().ff){
            cur = pq.top().ff;
            assert(!dist[pq.top().ss]);
            send(pq.top().ss, POINT);
            auto a = pq.top(); pq.pop();
            bfs(a);
        }else{
            if(w == 505)return;
            cur += w;
            pend(POINT);
        }
    }
    void receivePoint(int x){
        bfs({cur, x});
    }
};

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
	G.resize(N);
    dist.resize(N);
	for(int i = 0; i < A; i++){
		G[U[i]].pb({C[i], V[i]});
		G[V[i]].pb({C[i], U[i]});
	}
	bfs({1, 0});
}
void ReceiveA(bool x){
	static int cc = 0;
	cc = (cc<<1)+x;
	if(--pending)return;
	//cerr << "Azer: rece " << cc << endl;
    pendF?receivePoint(cc):receiveWeight(cc);
    cc = 0;
}
vector<int> Answer(){
    for(auto& i: dist)i--;
    return dist;
}

Baijan

#include<bits/stdc++.h>
#include "Baijan.h"
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef int64_t lld;
typedef pair<int, int> pii;

namespace {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<vector<pii>> G;
    vector<int> dist;

    const int POINT = 11, WEIGHT = 9;

    int pending = 0;
    bool pendF = false; // true: POINT, false: WEIGHT
    void pend(int len){
        assert(pending == 0);
        pendF = (len == POINT);
        pending = len;
        //cerr << "Baij: pend" << endl;
    }
    void send(int x, int len){
        for(int i = len-1; i >= 0; i--)
            SendB((x>>i)&1);
        //cerr << "Baij: send " << x << endl;
    }
    int cur = 0;
    void bfs(pii p){
        assert(!dist[p.ss]);
        dist[p.ss] = p.ff;
        for(auto i: G[p.ss]){
            if(dist[i.ss])
                continue;
            pq.push({i.ff+p.ff, i.ss});
        }
        while(!pq.empty() && dist[pq.top().ss])pq.pop();
        if(pq.empty())send(505, WEIGHT);
        else send(pq.top().ff-cur, WEIGHT);
        pend(WEIGHT);
    }

    void receiveWeight(int w){
        if(!pq.empty() && w + cur >= pq.top().ff){
            cur = pq.top().ff;
            assert(!dist[pq.top().ss]);
            send(pq.top().ss, POINT);
            auto a = pq.top(); pq.pop();
            bfs(a);
        }else{
            if(w == 505)return;
            cur += w;
            pend(POINT);
        }
    }
    void receivePoint(int x){
        bfs({cur, x});
    }
};

void InitB(int N, int B, vector<int> U, vector<int> V, vector<int> C) {
	G.resize(N);
    dist.resize(N);
	for(int i = 0; i < B; i++){
		G[U[i]].pb({C[i], V[i]});
		G[V[i]].pb({C[i], U[i]});
	}
	bfs({1, 0});
}
void ReceiveB(bool x){
    static int cc = 0;
	cc = (cc<<1)+x;
	if(--pending)return;
	//cerr << "Baij: rece " << cc << endl;
    pendF?receivePoint(cc):receiveWeight(cc);
    cc = 0;
}

• 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