답안 #836479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836479	2023-08-24T11:44:29 Z	_martynas	Two Transportations (JOI19_transportations)	C++14	100 / 100	691 ms	48884 KB

Azer
Baijan

#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) {
    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) {
    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);
    if(n == 1) return;
    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--;
    }
    if(tim > 0) return;
    if(!reading_location) {
        if(my_mn.fi <= val) {
            place(my_mn.se, mxdist+my_mn.fi);
            send_val(my_mn.se, mxloc);
            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);
        if(count(visited, visited+n, true) >= n) return;
        my_mn = get_min_dist_loc();
        send_val(my_mn.fi, mxval);
        read_val(mxval);
    }
}

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) {
    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) {
    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);
    if(n == 1) return;
    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--;
    }
    if(tim > 0) return;
    if(!reading_location) {
        if(my_mn.fi < val) {
            place(my_mn.se, mxdist+my_mn.fi);
            send_val(my_mn.se, mxloc);
            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);
        if(count(visited, visited+n, true) >= n) return;
        my_mn = get_min_dist_loc();
        send_val(my_mn.fi, mxval);
        read_val(mxval);
    }
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	358 ms	792 KB	Output is correct
2	Correct	0 ms	656 KB	Output is correct
3	Correct	362 ms	788 KB	Output is correct
4	Correct	370 ms	10092 KB	Output is correct
5	Correct	14 ms	912 KB	Output is correct
6	Correct	380 ms	2196 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	656 KB	Output is correct
2	Correct	370 ms	748 KB	Output is correct
3	Correct	400 ms	804 KB	Output is correct
4	Correct	494 ms	27504 KB	Output is correct
5	Correct	440 ms	24064 KB	Output is correct
6	Correct	66 ms	656 KB	Output is correct
7	Correct	568 ms	24312 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	358 ms	724 KB	Output is correct
2	Correct	0 ms	656 KB	Output is correct
3	Correct	404 ms	656 KB	Output is correct
4	Correct	407 ms	740 KB	Output is correct
5	Correct	428 ms	656 KB	Output is correct
6	Correct	425 ms	732 KB	Output is correct
7	Correct	380 ms	740 KB	Output is correct
8	Correct	354 ms	664 KB	Output is correct
9	Correct	418 ms	684 KB	Output is correct
10	Correct	389 ms	788 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	127 ms	684 KB	Output is correct
2	Correct	170 ms	656 KB	Output is correct
3	Correct	168 ms	13304 KB	Output is correct
4	Correct	178 ms	656 KB	Output is correct
5	Correct	237 ms	10080 KB	Output is correct
6	Correct	179 ms	656 KB	Output is correct
7	Correct	138 ms	732 KB	Output is correct
8	Correct	163 ms	656 KB	Output is correct
9	Correct	257 ms	18044 KB	Output is correct
10	Correct	292 ms	18104 KB	Output is correct
11	Correct	338 ms	35616 KB	Output is correct
12	Correct	302 ms	30668 KB	Output is correct
13	Correct	174 ms	656 KB	Output is correct
14	Correct	0 ms	656 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	127 ms	684 KB	Output is correct
2	Correct	170 ms	656 KB	Output is correct
3	Correct	168 ms	13304 KB	Output is correct
4	Correct	178 ms	656 KB	Output is correct
5	Correct	237 ms	10080 KB	Output is correct
6	Correct	179 ms	656 KB	Output is correct
7	Correct	138 ms	732 KB	Output is correct
8	Correct	163 ms	656 KB	Output is correct
9	Correct	257 ms	18044 KB	Output is correct
10	Correct	292 ms	18104 KB	Output is correct
11	Correct	338 ms	35616 KB	Output is correct
12	Correct	302 ms	30668 KB	Output is correct
13	Correct	174 ms	656 KB	Output is correct
14	Correct	0 ms	656 KB	Output is correct
15	Correct	169 ms	656 KB	Output is correct
16	Correct	219 ms	656 KB	Output is correct
17	Correct	185 ms	656 KB	Output is correct
18	Correct	276 ms	10120 KB	Output is correct
19	Correct	199 ms	660 KB	Output is correct
20	Correct	315 ms	10368 KB	Output is correct
21	Correct	186 ms	732 KB	Output is correct
22	Correct	254 ms	736 KB	Output is correct
23	Correct	353 ms	22140 KB	Output is correct
24	Correct	357 ms	22276 KB	Output is correct
25	Correct	369 ms	43544 KB	Output is correct
26	Correct	377 ms	36476 KB	Output is correct
27	Correct	243 ms	752 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	127 ms	684 KB	Output is correct
2	Correct	170 ms	656 KB	Output is correct
3	Correct	168 ms	13304 KB	Output is correct
4	Correct	178 ms	656 KB	Output is correct
5	Correct	237 ms	10080 KB	Output is correct
6	Correct	179 ms	656 KB	Output is correct
7	Correct	138 ms	732 KB	Output is correct
8	Correct	163 ms	656 KB	Output is correct
9	Correct	257 ms	18044 KB	Output is correct
10	Correct	292 ms	18104 KB	Output is correct
11	Correct	338 ms	35616 KB	Output is correct
12	Correct	302 ms	30668 KB	Output is correct
13	Correct	174 ms	656 KB	Output is correct
14	Correct	0 ms	656 KB	Output is correct
15	Correct	169 ms	656 KB	Output is correct
16	Correct	219 ms	656 KB	Output is correct
17	Correct	185 ms	656 KB	Output is correct
18	Correct	276 ms	10120 KB	Output is correct
19	Correct	199 ms	660 KB	Output is correct
20	Correct	315 ms	10368 KB	Output is correct
21	Correct	186 ms	732 KB	Output is correct
22	Correct	254 ms	736 KB	Output is correct
23	Correct	353 ms	22140 KB	Output is correct
24	Correct	357 ms	22276 KB	Output is correct
25	Correct	369 ms	43544 KB	Output is correct
26	Correct	377 ms	36476 KB	Output is correct
27	Correct	243 ms	752 KB	Output is correct
28	Correct	277 ms	656 KB	Output is correct
29	Correct	262 ms	664 KB	Output is correct
30	Correct	377 ms	24016 KB	Output is correct
31	Correct	225 ms	656 KB	Output is correct
32	Correct	361 ms	21028 KB	Output is correct
33	Correct	261 ms	800 KB	Output is correct
34	Correct	338 ms	760 KB	Output is correct
35	Correct	270 ms	768 KB	Output is correct
36	Correct	393 ms	24728 KB	Output is correct
37	Correct	449 ms	24704 KB	Output is correct
38	Correct	497 ms	48884 KB	Output is correct
39	Correct	468 ms	44284 KB	Output is correct
40	Correct	271 ms	912 KB	Output is correct

Subtask #7
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	358 ms	792 KB	Output is correct
2	Correct	0 ms	656 KB	Output is correct
3	Correct	362 ms	788 KB	Output is correct
4	Correct	370 ms	10092 KB	Output is correct
5	Correct	14 ms	912 KB	Output is correct
6	Correct	380 ms	2196 KB	Output is correct
7	Correct	0 ms	656 KB	Output is correct
8	Correct	370 ms	748 KB	Output is correct
9	Correct	400 ms	804 KB	Output is correct
10	Correct	494 ms	27504 KB	Output is correct
11	Correct	440 ms	24064 KB	Output is correct
12	Correct	66 ms	656 KB	Output is correct
13	Correct	568 ms	24312 KB	Output is correct
14	Correct	358 ms	724 KB	Output is correct
15	Correct	0 ms	656 KB	Output is correct
16	Correct	404 ms	656 KB	Output is correct
17	Correct	407 ms	740 KB	Output is correct
18	Correct	428 ms	656 KB	Output is correct
19	Correct	425 ms	732 KB	Output is correct
20	Correct	380 ms	740 KB	Output is correct
21	Correct	354 ms	664 KB	Output is correct
22	Correct	418 ms	684 KB	Output is correct
23	Correct	389 ms	788 KB	Output is correct
24	Correct	127 ms	684 KB	Output is correct
25	Correct	170 ms	656 KB	Output is correct
26	Correct	168 ms	13304 KB	Output is correct
27	Correct	178 ms	656 KB	Output is correct
28	Correct	237 ms	10080 KB	Output is correct
29	Correct	179 ms	656 KB	Output is correct
30	Correct	138 ms	732 KB	Output is correct
31	Correct	163 ms	656 KB	Output is correct
32	Correct	257 ms	18044 KB	Output is correct
33	Correct	292 ms	18104 KB	Output is correct
34	Correct	338 ms	35616 KB	Output is correct
35	Correct	302 ms	30668 KB	Output is correct
36	Correct	174 ms	656 KB	Output is correct
37	Correct	0 ms	656 KB	Output is correct
38	Correct	169 ms	656 KB	Output is correct
39	Correct	219 ms	656 KB	Output is correct
40	Correct	185 ms	656 KB	Output is correct
41	Correct	276 ms	10120 KB	Output is correct
42	Correct	199 ms	660 KB	Output is correct
43	Correct	315 ms	10368 KB	Output is correct
44	Correct	186 ms	732 KB	Output is correct
45	Correct	254 ms	736 KB	Output is correct
46	Correct	353 ms	22140 KB	Output is correct
47	Correct	357 ms	22276 KB	Output is correct
48	Correct	369 ms	43544 KB	Output is correct
49	Correct	377 ms	36476 KB	Output is correct
50	Correct	243 ms	752 KB	Output is correct
51	Correct	277 ms	656 KB	Output is correct
52	Correct	262 ms	664 KB	Output is correct
53	Correct	377 ms	24016 KB	Output is correct
54	Correct	225 ms	656 KB	Output is correct
55	Correct	361 ms	21028 KB	Output is correct
56	Correct	261 ms	800 KB	Output is correct
57	Correct	338 ms	760 KB	Output is correct
58	Correct	270 ms	768 KB	Output is correct
59	Correct	393 ms	24728 KB	Output is correct
60	Correct	449 ms	24704 KB	Output is correct
61	Correct	497 ms	48884 KB	Output is correct
62	Correct	468 ms	44284 KB	Output is correct
63	Correct	271 ms	912 KB	Output is correct
64	Correct	470 ms	960 KB	Output is correct
65	Correct	550 ms	26476 KB	Output is correct
66	Correct	473 ms	23312 KB	Output is correct
67	Correct	416 ms	932 KB	Output is correct
68	Correct	415 ms	932 KB	Output is correct
69	Correct	483 ms	47604 KB	Output is correct
70	Correct	691 ms	39460 KB	Output is correct
71	Correct	478 ms	5008 KB	Output is correct
72	Correct	373 ms	1168 KB	Output is correct

답안 #836479

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 8.0 / 8.0

Subtask #4 38.0 / 38.0

Subtask #5 14.0 / 14.0

Subtask #6 10.0 / 10.0

Subtask #7 16.0 / 16.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
8.0 / 8.0

Subtask #4
38.0 / 38.0

Subtask #5
14.0 / 14.0

Subtask #6
10.0 / 10.0

Subtask #7
16.0 / 16.0