oj.uz

Submission #836460

# Submission time Handle Problem Language Result Execution time Memory
836460 2023-08-24T11:31:12 Z _martynas Two Transportations (JOI19_transportations) C++17
0 / 100
 371 ms 35640 KB 
#include "Azer.h"
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int mxn = 2001;
const int mxval = 9;
const int mxloc = 11;
const int inf = 1e6;

namespace {
int n;
vector<pair<int, int>> adj[mxn];
bool visited[mxn];
vector<int> dist;
int mxdist = 0;

void send_val(int x, int bits) {
    // printf("A: send x = %d, bits = %d\n", x, bits);
    vector<bool> send;
    for(int i = 0; i < bits; i++) {
        send.push_back(x % 2 == 1);
        x /= 2;
    }
    reverse(send.begin(), send.end());
    for(bool x : send) SendA(x);
}

int val = 0, tim = 0;
void read_val(int t) {
    // printf("A: read x for t = %d\n", t);
    val = 0;
    tim = t;
}

void place(int u, int d) {
    visited[u] = true; dist[u] = d;
    for(auto e : adj[u]) dist[e.fi] = min(dist[e.fi], dist[u]+e.se);
    mxdist = max(mxdist, dist[u]);
}

int gotd = 0;
bool reading_location = false;
pair<int, int> my_mn;
pair<int, int> get_min_dist_loc() {
    pair<int, int> res = {(1<<mxval)-1, (1<<mxloc)-1};
    for(int i = 0; i < n; i++) if(!visited[i] && dist[i] < inf) {
        if(dist[i]-mxdist < res.fi) {
            res = {dist[i]-mxdist, i};
        }
    }
    return res;
}
}  // 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++) {
        adj[U[i]].push_back({V[i], C[i]});
        adj[V[i]].push_back({U[i], C[i]});
    }
    dist = vector<int>(n, inf);
    place(0, 0);
    my_mn = get_min_dist_loc();
    send_val(my_mn.fi, mxval);
    read_val(mxval);
}

void ReceiveA(bool x) {
    if(tim > 0) {
        val = 2*val+x;
        tim--;
        // printf("A: tim = %d, val = %d\n", tim, val);
    }
    if(tim > 0) return;
    // printf("A: val = %d, gotd = %d, read loc = %d\n", val, gotd, reading_location);
    if(!reading_location) {
        // !!! Need asymmetry !!!
        if(my_mn.fi <= val) {
            place(my_mn.se, mxdist+my_mn.fi);
            send_val(my_mn.se, mxloc);
            // send the next mn dist
            if(count(visited, visited+n, true) >= n) return;
            my_mn = get_min_dist_loc();
            send_val(my_mn.fi, mxval);
            read_val(mxval);
        }
        else {
            reading_location = true;
            gotd = val;
            read_val(mxloc);
        }
    }
    else {
        reading_location = false;
        place(val, mxdist+gotd);
        // send the next mn dist
        if(count(visited, visited+n, true) >= n) return;
        my_mn = get_min_dist_loc();
        send_val(my_mn.fi, mxval);
        read_val(mxval);
    }
    // printf("A dist: ");
    // for(int i = 0; i < n; i++) printf("%d, ", dist[i]);
    // printf("\n");
    // printf("A visited: ");
    // for(int i = 0; i < n; i++) printf("%d, ", visited[i]);
    // printf("\n");
}

vector<int> Answer() {
    return dist;
}

#include "Baijan.h"
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int mxn = 2001;
const int mxval = 9;
const int mxloc = 11;
const int inf = 1e6;

namespace {
int n;
vector<pair<int, int>> adj[mxn];
bool visited[mxn];
vector<int> dist;
int mxdist = 0;

void send_val(int x, int bits) {
    // printf("B: send x = %d, bits = %d\n", x, bits);
    vector<bool> send;
    for(int i = 0; i < bits; i++) {
        send.push_back(x % 2 == 1);
        x /= 2;
    }
    reverse(send.begin(), send.end());
    for(bool x : send) SendB(x);
}

int val = 0, tim = 0;
void read_val(int t) {
    // printf("B: read x for t = %d\n", t);
    val = 0;
    tim = t;
}

void place(int u, int d) {
    visited[u] = true; dist[u] = d;
    for(auto e : adj[u]) dist[e.fi] = min(dist[e.fi], dist[u]+e.se);
    mxdist = max(mxdist, dist[u]);
}

int gotd = 0;
bool reading_location = false;
pair<int, int> my_mn;
pair<int, int> get_min_dist_loc() {
    pair<int, int> res = {(1<<mxval)-1, (1<<mxloc)-1};
    for(int i = 0; i < n; i++) if(!visited[i] && dist[i] < inf) {
        if(dist[i]-mxdist < res.fi) {
            res = {dist[i]-mxdist, i};
        }
    }
    return res;
}

}  // namespace


void InitB(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n = N;
    for(int i = 0; i < A; i++) {
        adj[U[i]].push_back({V[i], C[i]});
        adj[V[i]].push_back({U[i], C[i]});
    }
    dist = vector<int>(n, inf);
    place(0, 0);
    my_mn = get_min_dist_loc();
    send_val(my_mn.fi, mxval);
    read_val(mxval);
}

void ReceiveB(bool x) {
    if(tim > 0) {
        val = 2*val+x;
        tim--;
        // printf("B: tim = %d, val = %d\n", tim, val);
    }
    if(tim > 0) return;
    // printf("B: val = %d, gotd = %d, read loc = %d\n", val, gotd, reading_location);
    if(!reading_location) {
        // !!! Need asymmetry !!!
        if(my_mn.fi < val) {
            place(my_mn.se, mxdist+my_mn.fi);
            send_val(my_mn.se, mxloc);
            // send the next mn dist
            if(count(visited, visited+n, true) >= n) return;
            my_mn = get_min_dist_loc();
            send_val(my_mn.fi, mxval);
            read_val(mxval);
        }
        else {
            reading_location = true;
            gotd = val;
            read_val(mxloc);
        }
    }
    else {
        reading_location = false;
        place(val, mxdist+gotd);
        // send the next mn dist
        if(count(visited, visited+n, true) >= n) return;
        my_mn = get_min_dist_loc();
        send_val(my_mn.fi, mxval);
        read_val(mxval);
    }
    // printf("B dist: ");
    // for(int i = 0; i < n; i++) printf("%d, ", dist[i]);
    // printf("\n");
    // printf("B visited: ");
    // for(int i = 0; i < n; i++) printf("%d, ", visited[i]);
    // printf("\n");
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 788 KB Output is correct
2 Runtime error 1 ms 456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 728 KB Output is correct
2 Runtime error 1 ms 456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 676 KB Output is correct
2 Correct 168 ms 660 KB Output is correct
3 Correct 251 ms 13300 KB Output is correct
4 Correct 202 ms 656 KB Output is correct
5 Correct 226 ms 10116 KB Output is correct
6 Correct 122 ms 656 KB Output is correct
7 Correct 127 ms 724 KB Output is correct
8 Correct 200 ms 656 KB Output is correct
9 Correct 248 ms 18036 KB Output is correct
10 Correct 229 ms 18188 KB Output is correct
11 Correct 292 ms 35640 KB Output is correct
12 Correct 288 ms 30656 KB Output is correct
13 Correct 177 ms 656 KB Output is correct
14 Runtime error 1 ms 464 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 676 KB Output is correct
2 Correct 168 ms 660 KB Output is correct
3 Correct 251 ms 13300 KB Output is correct
4 Correct 202 ms 656 KB Output is correct
5 Correct 226 ms 10116 KB Output is correct
6 Correct 122 ms 656 KB Output is correct
7 Correct 127 ms 724 KB Output is correct
8 Correct 200 ms 656 KB Output is correct
9 Correct 248 ms 18036 KB Output is correct
10 Correct 229 ms 18188 KB Output is correct
11 Correct 292 ms 35640 KB Output is correct
12 Correct 288 ms 30656 KB Output is correct
13 Correct 177 ms 656 KB Output is correct
14 Runtime error 1 ms 464 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 676 KB Output is correct
2 Correct 168 ms 660 KB Output is correct
3 Correct 251 ms 13300 KB Output is correct
4 Correct 202 ms 656 KB Output is correct
5 Correct 226 ms 10116 KB Output is correct
6 Correct 122 ms 656 KB Output is correct
7 Correct 127 ms 724 KB Output is correct
8 Correct 200 ms 656 KB Output is correct
9 Correct 248 ms 18036 KB Output is correct
10 Correct 229 ms 18188 KB Output is correct
11 Correct 292 ms 35640 KB Output is correct
12 Correct 288 ms 30656 KB Output is correct
13 Correct 177 ms 656 KB Output is correct
14 Runtime error 1 ms 464 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 788 KB Output is correct
2 Runtime error 1 ms 456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -