제출 #836465

#제출 시각아이디문제언어결과실행 시간메모리
836465_martynasTwo Transportations (JOI19_transportations)C++14
0 / 100
398 ms35628 KiB
#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"); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...