oj.uz

Submission #836465

# Submission time Handle Problem Language Result Execution time Memory
836465 2023-08-24T11:35:39 Z _martynas Two Transportations (JOI19_transportations) C++14
0 / 100
 398 ms 35628 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;
    if(n == 1) return;
    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;
    if(n == 1) return;
    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 366 ms 784 KB Output is correct
2 Incorrect 1 ms 328 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 328 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 724 KB Output is correct
2 Incorrect 0 ms 328 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 684 KB Output is correct
2 Correct 180 ms 656 KB Output is correct
3 Correct 185 ms 13324 KB Output is correct
4 Correct 169 ms 708 KB Output is correct
5 Correct 228 ms 10040 KB Output is correct
6 Correct 195 ms 656 KB Output is correct
7 Correct 130 ms 728 KB Output is correct
8 Correct 194 ms 656 KB Output is correct
9 Correct 301 ms 17992 KB Output is correct
10 Correct 276 ms 18168 KB Output is correct
11 Correct 316 ms 35628 KB Output is correct
12 Correct 299 ms 30500 KB Output is correct
13 Correct 183 ms 656 KB Output is correct
14 Incorrect 0 ms 328 KB Wrong Answer [1]
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 684 KB Output is correct
2 Correct 180 ms 656 KB Output is correct
3 Correct 185 ms 13324 KB Output is correct
4 Correct 169 ms 708 KB Output is correct
5 Correct 228 ms 10040 KB Output is correct
6 Correct 195 ms 656 KB Output is correct
7 Correct 130 ms 728 KB Output is correct
8 Correct 194 ms 656 KB Output is correct
9 Correct 301 ms 17992 KB Output is correct
10 Correct 276 ms 18168 KB Output is correct
11 Correct 316 ms 35628 KB Output is correct
12 Correct 299 ms 30500 KB Output is correct
13 Correct 183 ms 656 KB Output is correct
14 Incorrect 0 ms 328 KB Wrong Answer [1]
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 684 KB Output is correct
2 Correct 180 ms 656 KB Output is correct
3 Correct 185 ms 13324 KB Output is correct
4 Correct 169 ms 708 KB Output is correct
5 Correct 228 ms 10040 KB Output is correct
6 Correct 195 ms 656 KB Output is correct
7 Correct 130 ms 728 KB Output is correct
8 Correct 194 ms 656 KB Output is correct
9 Correct 301 ms 17992 KB Output is correct
10 Correct 276 ms 18168 KB Output is correct
11 Correct 316 ms 35628 KB Output is correct
12 Correct 299 ms 30500 KB Output is correct
13 Correct 183 ms 656 KB Output is correct
14 Incorrect 0 ms 328 KB Wrong Answer [1]
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 784 KB Output is correct
2 Incorrect 1 ms 328 KB Wrong Answer [1]
3 Halted 0 ms 0 KB -