Submission #963502

#	Time	Username	Problem	Language	Result	Execution time	Memory
963502		GrindMachine	Two Transportations (JOI19_transportations)	C++17	62 / 100	910 ms	60268 KiB

Azer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/88408 (dial's algorithm tutorial)

*/

#include "Azer.h"

namespace {

    int n;
    vector<int> a;
    vector<vector<pii>> adj;
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    vector<bool> vis;
    vector<int> ans;
    int prev_cost = 0;

    void send(){
        if(pq.empty()){
            rep(iter,20){
                SendA(0);
            }
        }
        else{
            auto [w,u] = pq.top();
            w -= prev_cost;
            assert(w < (1<<9));
            rep(i,9){
                int f = 1<<(9-i-1);
                int b = 0;
                if(w&f) b = 1;
                SendA(b);
            }
            rep(i,11){
                int f = 1<<(11-i-1);
                int b = 0;
                if(u&f) b = 1;
                SendA(b);
            }
        }
    }

}  // namespace

void InitA(int n_, int m, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n = n_;
    adj.resize(n);
    ans.resize(n);
    vis.resize(n);

    rep(i,m) {
        int u = U[i], v = V[i], w = C[i];
        adj[u].pb({v,w}), adj[v].pb({u,w});        
    }

    vis[0] = 1;

    for(auto [v,w] : adj[0]){
        pq.push({w,v});
    }

    send();
}

void ReceiveA(bool x) {
    a.pb(x);
    if(sz(a) == 20){
        int w = 0;
        rep(i,9){
            w = (w<<1)|a[i];
        }
        int u = 0;
        for(int i = 9; i < 20; ++i){
            u = (u<<1)|a[i];
        }

        w += prev_cost;

        // cout << "A" << endl;
        // cout << u << " " << w << endl;
        
        a.clear();

        if(u == 0) return;

        ans[u] = w;
        vis[u] = 1;
        prev_cost = w;

        for(auto [v,ww] : adj[u]){
            pq.push({w+ww,v});
        }

        while(!pq.empty()){
            auto [cost,u] = pq.top();
            if(vis[u]){
                pq.pop();
                conts;
            }
            break;
        }

        send();
    }
}

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

Baijan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*


refs:
https://codeforces.com/blog/entry/88408 (dial's algorithm tutorial)

*/

#include "Baijan.h"

const int inf1 = 1e9 + 5;

namespace {

    vector<vector<pii>> adj;
    vector<int> a;
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    vector<bool> vis;
    vector<array<int,3>> sp_tree;
    vector<array<int,3>> edges;
    int prev_cost = 0;

    void send(int w, int u){
        w -= prev_cost;
        assert(w < (1<<9));
        rep(i,9){
            int f = 1<<(9-i-1);
            int b = 0;
            if(w&f) b = 1;
            SendB(b);
        }
        rep(i,11){
            int f = 1<<(11-i-1);
            int b = 0;
            if(u&f) b = 1;
            SendB(b);
        }
    }

}  // namespace

void InitB(int n, int m, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
        
    adj.resize(n);
    vis.resize(n);

    rep(i,m){
        int u = S[i], v = T[i], w = D[i];
        adj[u].pb({v,w}), adj[v].pb({u,w});
    }

    vis[0] = 1;

    for(auto [v,w] : adj[0]){
        pq.push({w,v});
    }
}

void ReceiveB(bool y) {
    a.pb(y);
    if(sz(a) == 20){
        int w = 0;
        rep(i,9){
            w = (w<<1)|a[i];
        }
        int u = 0;
        for(int i = 9; i < 20; ++i){
            u = (u<<1)|a[i];
        }

        a.clear();

        w += prev_cost;
        if(u == 0){
            w = inf1;
        }

        // cout << "B" << endl;
        // cout << u << " " << w << endl;

        while(!pq.empty()){
            auto [cost,u] = pq.top();
            if(vis[u]){
                pq.pop();
                conts;
            }

            break;
        }

        if(!pq.empty()){
            if(pq.top().ff < w){
                w = pq.top().ff;
                u = pq.top().ss;
            }
        }

        if(w == inf1) w = prev_cost;
        send(w,u);
        prev_cost = w;
        vis[u] = 1;

        for(auto [v,ww] : adj[u]){
            pq.push({w+ww,v});
        }
    }
}

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