Submission #245485

#	Time	Username	Problem	Language	Result	Execution time	Memory
245485		pavel	Two Transportations (JOI19_transportations)	C++14	100 / 100	1914 ms	113712 KiB

Azer

#include "Azer.h"
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;
typedef pair<int,int> ii;

namespace {
    const int MAXN = 2003;
    int n;
    bool done[MAXN];
    int dc=0;
    vector<int> solA;
    priority_queue<ii> e;
    vector<ii> graph[MAXN];
    int pre=0;
    int idx=0;
    int cA, cB;
    int nA, nB;



    void add_node(int val, int node){
        //printf("A add_node(%d %d)\n", val, node);
        pre = val;
        solA[node] = val;
        done[node] = true;
        dc++;
        for(auto i:graph[node]){
            e.push(ii(-solA[node] + i.first, i.second));
        }
    }

    void send_best(){
        if(dc == n) return;
        cA = (1<<9)-1;
        nA = -1;
        while(!e.empty() && done[e.top().second]) e.pop();
        if(!e.empty()){
            cA = (-e.top().first) - pre;
            nA = e.top().second;
        }
        //printf("A send_best() -> %d\n", cA);
        for(int i=0;i<9;++i) SendA((1<<i) & cA);
    }
}

void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c) {
    ::n = n;
    solA.resize(n);
    for(int i=0;i<a;++i){
        graph[u[i]].push_back(ii(-c[i], v[i]));
        graph[v[i]].push_back(ii(-c[i], u[i]));
    }
    add_node(0, 0);
    send_best();
}

void ReceiveA(bool x) {
    if(idx<9){
        cB |= ((int)x) << idx;
        idx++;
        if(idx == 9){
            //printf("A recieved cB %d\n", cB);
            if(cB > cA){
                add_node(pre + cA, nA);
                for(int i = 0; i < 11; i++){
                    SendA((1<<i) & nA);
                }
                idx = 0;
                cB = 0; nB = 0;
                send_best();
            }
        }
    }else{
        nB |= ((int)x) << (idx - 9);
        idx++;
        if(idx == 20){
            //printf("A recieved nB %d\n", nB);
            add_node(pre + cB, nB);
            idx = 0;
            cB = 0; nB = 0;
            send_best();
        }
    }
}

std::vector<int> Answer() {
    return vector<int>(solA);
}

Baijan

#include "Baijan.h"
#include <vector>
#include <queue>
#include <cstdio>
#ifdef EVAL
#define dbg(x) ;
#else
#define dbg(x) //printf(x)
#endif

using namespace std;
typedef pair<int,int> ii;

namespace {
    const int MAXN = 2003;
    int n;
    bool done[MAXN];
    int dc=0;
    vector<int> solB;
    priority_queue<ii> e;
    vector<ii> graph[MAXN];
    int pre=0;
    int idx=0;
    int cA, cB;
    int nA, nB;



    void add_node(int val, int node){
        //printf("B add_node(%d %d)\n", val, node);
        pre = val;
        solB[node] = val;
        done[node] = true;
        dc++;
        for(auto i:graph[node]){
            e.push(ii(-solB[node] + i.first, i.second));
        }
    }

    void send_best(){
        if(dc == n) return;
        cB = (1<<9)-1;
        nB = -1;
        while(!e.empty() && done[e.top().second]) e.pop();
        if(!e.empty()){
            cB = (-e.top().first) - pre;
            nB = e.top().second;
        }
        //printf("B send_best() -> %d\n", cB);
        for(int i=0;i<9;++i) SendB((1<<i) & cB);
    }
}

void InitB(int n, int a, vector<int> u, vector<int> v, vector<int> c) {
    ::n = n;
    solB.resize(n);
    for(int i=0;i<a;++i){
        graph[u[i]].push_back(ii(-c[i], v[i]));
        graph[v[i]].push_back(ii(-c[i], u[i]));
    }
    add_node(0, 0);
}

void ReceiveB(bool x) {
    if(idx<9){
        cA |= ((int)x) << idx;
        idx++;
        if(idx == 9){
            //printf("B recieved cA %d\n", cA);
            send_best();
            if(cA >= cB){
                add_node(pre + cB, nB);
                for(int i = 0; i < 11; i++){
                    SendB((1<<i) & nB);
                }
                idx = 0;
                cA = 0; nA = 0;
            }
        }
    }else{
        nA |= ((int)x) << (idx - 9);
        idx++;
        if(idx == 20){
            //printf("B recieved nA %d\n", nA);
            add_node(pre + cA, nA);
            idx = 0;
            cA = 0; nA = 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