Submission #414934

#	Time	Username	Problem	Language	Result	Execution time	Memory
414934		Pro_ktmr	Two Transportations (JOI19_transportations)	C++17	100 / 100	1024 ms	48948 KiB

Azer

#include"Azer.h"

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)

namespace A{
    int N;
    vector<pair<int,int>> e[2000];
    vector<bool> decided;
    int dcnt = 0;
    vector<int> cost;

    int state = 0;
    int cnt = 0;

    int send = 0;
    int receive = 0;
    int idx = 0;
    int bef = 0;
    priority_queue<pair<int,int>> pq;

    void Dijkstra(int n, int v){
        v = bef + v;
        bef = v;
        decided[n] = true;
        cost[n] = v;
        dcnt++;
        if(dcnt == N) return;

        //cout << "A1: " << n << " " << v << endl;

        rep(i, e[n].size()){
            if(cost[e[n][i].first] > v + e[n][i].second){
                cost[e[n][i].first] = v + e[n][i].second;
                pq.push({-cost[e[n][i].first], e[n][i].first});
            }
        }

        while(!pq.empty() && decided[pq.top().second]) pq.pop();
        if(pq.empty()) send = 501;
        else send = -pq.top().first - bef;
        rep(i, 9) SendA((send>>8-i)&1);

        if(pq.empty()) idx = 2000;
        else idx = pq.top().second;

        //cout << "A2: " << idx << " " << send+bef << endl;
    }
}  // namespace

void InitA(int _N, int A, vector<int> U, vector<int> V, vector<int> C) {
    using namespace A;
    N = _N;
    rep(i, A){
        e[U[i]].pb({V[i], C[i]});
        e[V[i]].pb({U[i], C[i]});
    }
    decided.assign(N, false);
    cost.assign(N, INT_MAX);

    Dijkstra(0, 0);
}

void ReceiveA(bool x) {
    using namespace A;
    if(state == 0){
        receive = (receive<<1) + x;
        cnt++;
        if(cnt == 9){
            cnt = 0;
            if(send <= receive){
                rep(i, 11) SendA((idx>>10-i)&1);
                Dijkstra(idx, send);
                receive = 0;
            }
            else{
                state = 1;
                idx = 0;
            }
        }
    }
    else{
        idx = (idx<<1) + x;
        cnt++;
        if(cnt == 11){
            cnt = 0;
            state = 0;
            Dijkstra(idx, receive);
            receive = 0;
        }
    }
}

vector<int> Answer() {
    using namespace A;
    return cost;
}

Baijan

#include"Baijan.h"

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)

namespace B{
    int N;
    vector<pair<int,int>> e[2000];
    vector<bool> decided;
    int dcnt = 0;
    vector<int> cost;

    int state = 0;
    int cnt = 0;

    int send = 0;
    int receive = 0;
    int idx = 0;
    int bef = 0;
    priority_queue<pair<int,int>> pq;

    void Dijkstra(int n, int v){
        v = bef + v;
        bef = v;
        decided[n] = true;
        cost[n] = v;
        dcnt++;
        if(dcnt == N) return;

        //cout << "B1: " << n << " " << v << endl;

        rep(i, e[n].size()){
            if(cost[e[n][i].first] > v + e[n][i].second){
                cost[e[n][i].first] = v + e[n][i].second;
                pq.push({-cost[e[n][i].first], e[n][i].first});
            }
        }

        while(!pq.empty() && decided[pq.top().second]) pq.pop();
        if(pq.empty()) send = 501;
        else send = -pq.top().first - bef;
        rep(i, 9) SendB((send>>8-i)&1);

        if(pq.empty()) idx = 2000;
        else idx = pq.top().second;

        //cout << "B2: " << idx << " " << send+bef << endl;
    }
}  // namespace

void InitB(int _N, int B, vector<int> S, vector<int> T, vector<int> D) {
    using namespace B;
    N = _N;
    rep(i, B){
        e[S[i]].pb({T[i], D[i]});
        e[T[i]].pb({S[i], D[i]});
    }
    decided.assign(N, false);
    cost.assign(N, INT_MAX);

    Dijkstra(0, 0);
}

void ReceiveB(bool y) {
    using namespace B;
    if(state == 0){
        receive = (receive<<1) + y;
        cnt++;
        if(cnt == 9){
            cnt = 0;
            if(send < receive){
                rep(i, 11) SendB((idx>>10-i)&1);
                Dijkstra(idx, send);
                receive = 0;
            }
            else{
                state = 1;
                idx = 0;
            }
        }
    }
    else{
        idx = (idx<<1) + y;
        cnt++;
        if(cnt == 11){
            cnt = 0;
            state = 0;
            Dijkstra(idx, receive);
            receive = 0;
        }
    }
}

Compilation message (stderr)

Azer.cpp: In function 'void A::Dijkstra(int, int)':
Azer.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Azer.cpp:41:9: note: in expansion of macro 'rep'
   41 |         rep(i, e[n].size()){
      |         ^~~
Azer.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Azer.cpp:51:9: note: in expansion of macro 'rep'
   51 |         rep(i, 9) SendA((send>>8-i)&1);
      |         ^~~
Azer.cpp:51:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   51 |         rep(i, 9) SendA((send>>8-i)&1);
      |                                ~^~
Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Azer.cpp:63:5: note: in expansion of macro 'rep'
   63 |     rep(i, A){
      |     ^~~
Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Azer.cpp:81:17: note: in expansion of macro 'rep'
   81 |                 rep(i, 11) SendA((idx>>10-i)&1);
      |                 ^~~
Azer.cpp:81:42: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   81 |                 rep(i, 11) SendA((idx>>10-i)&1);
      |                                        ~~^~

Baijan.cpp: In function 'void B::Dijkstra(int, int)':
Baijan.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Baijan.cpp:41:9: note: in expansion of macro 'rep'
   41 |         rep(i, e[n].size()){
      |         ^~~
Baijan.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Baijan.cpp:51:9: note: in expansion of macro 'rep'
   51 |         rep(i, 9) SendB((send>>8-i)&1);
      |         ^~~
Baijan.cpp:51:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   51 |         rep(i, 9) SendB((send>>8-i)&1);
      |                                ~^~
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Baijan.cpp:63:5: note: in expansion of macro 'rep'
   63 |     rep(i, B){
      |     ^~~
Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:13:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Baijan.cpp:81:17: note: in expansion of macro 'rep'
   81 |                 rep(i, 11) SendB((idx>>10-i)&1);
      |                 ^~~
Baijan.cpp:81:42: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   81 |                 rep(i, 11) SendB((idx>>10-i)&1);
      |                                        ~~^~

• 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