oj.uz

Submission #836416

# Submission time Handle Problem Language Result Execution time Memory
836416 2023-08-24T11:02:10 Z _martynas Two Transportations (JOI19_transportations) C++14
0 / 100
 439 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;
    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 439 ms 784 KB Output is correct
2 Runtime error 1 ms 468 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 476 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 337 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 232 ms 656 KB Output is correct
2 Correct 238 ms 660 KB Output is correct
3 Correct 226 ms 13172 KB Output is correct
4 Correct 185 ms 656 KB Output is correct
5 Correct 223 ms 10024 KB Output is correct
6 Correct 178 ms 668 KB Output is correct
7 Correct 199 ms 656 KB Output is correct
8 Correct 173 ms 724 KB Output is correct
9 Correct 265 ms 18164 KB Output is correct
10 Correct 280 ms 18204 KB Output is correct
11 Correct 377 ms 35628 KB Output is correct
12 Correct 356 ms 30540 KB Output is correct
13 Correct 174 ms 656 KB Output is correct
14 Runtime error 1 ms 456 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 232 ms 656 KB Output is correct
2 Correct 238 ms 660 KB Output is correct
3 Correct 226 ms 13172 KB Output is correct
4 Correct 185 ms 656 KB Output is correct
5 Correct 223 ms 10024 KB Output is correct
6 Correct 178 ms 668 KB Output is correct
7 Correct 199 ms 656 KB Output is correct
8 Correct 173 ms 724 KB Output is correct
9 Correct 265 ms 18164 KB Output is correct
10 Correct 280 ms 18204 KB Output is correct
11 Correct 377 ms 35628 KB Output is correct
12 Correct 356 ms 30540 KB Output is correct
13 Correct 174 ms 656 KB Output is correct
14 Runtime error 1 ms 456 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 232 ms 656 KB Output is correct
2 Correct 238 ms 660 KB Output is correct
3 Correct 226 ms 13172 KB Output is correct
4 Correct 185 ms 656 KB Output is correct
5 Correct 223 ms 10024 KB Output is correct
6 Correct 178 ms 668 KB Output is correct
7 Correct 199 ms 656 KB Output is correct
8 Correct 173 ms 724 KB Output is correct
9 Correct 265 ms 18164 KB Output is correct
10 Correct 280 ms 18204 KB Output is correct
11 Correct 377 ms 35628 KB Output is correct
12 Correct 356 ms 30540 KB Output is correct
13 Correct 174 ms 656 KB Output is correct
14 Runtime error 1 ms 456 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 439 ms 784 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -