#include "Azer.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 2000;
const int LOG_N = 11;
const int LOG_D = 20;
namespace {
int N;
vector<pii> gp[MAX_N+1];
int dist[MAX_N+1];
int vst[MAX_N+1];
int n, d, cnt;
int n2, d2;
bool finish = false;
void calc(){
for(int i=0; i<gp[n].size(); i++){
if(dist[gp[n][i].first]>dist[n] + gp[n][i].second){
dist[gp[n][i].first] = dist[n] + gp[n][i].second;
}
}
n2 = 0;
d2 = (1<<LOG_D)-1;
finish = true;
for(int i=0; i<N; i++){
if(!vst[i]) finish = false;
if(vst[i]) continue;
if(dist[i] < d2){
d2 = dist[i];
n2 = i;
}
}
}
void make_ans(){
bool b = true;
if(d<d2){
dist[n] = d;
vst[n] = true;
}else{
b = false;
dist[n2] = d2;
n = n2; d = d2;
vst[n] = true;
}
calc();
if(finish){
Answer();
return;
}
if(b){
n = d = cnt = 0;
SendA(1);
return;
}
SendA(0);
n = n2; d = d2;
for(int i=0; i<LOG_N; i++){
SendA(n%2); n/=2;
}for(int i=0; i<LOG_D; i++){
SendA(d%2); d/=2;
}
n = d = cnt = 0;
}
}
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
::N = N;
for (int i = 0; i < A; ++i) {
gp[U[i]].pb({V[i], C[i]});
gp[V[i]].pb({U[i], C[i]});
}
vst[0] = 0;
for(int i=1; i<N; i++){
dist[i] = (1<<LOG_D)-1;
}
calc();
}
void ReceiveA(bool x) {
if(cnt<LOG_N){
n = n*2 + (int)x;
}else if(cnt < LOG_D){
d = d*2 + (int)x;
}
cnt++;
if(cnt==LOG_D){
make_ans();
}
}
vector<int> Answer() {
vector<int> ans(N);
for(int i=0; i<N; i++){
ans[i] = dist[i];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
const int MAX_N = 2000;
const int LOG_N = 11;
const int LOG_D = 20;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
namespace {
int N;
vector<pii> gp[MAX_N+1];
int dist[MAX_N+1];
int vst[MAX_N+1];
int n=0, d=0, cnt=0;
bool finish = false;
void calc(){
for(int i=0; i<gp[n].size(); i++){
if(dist[gp[n][i].first]>dist[n] + gp[n][i].second){
dist[gp[n][i].first] = dist[n] + gp[n][i].second;
}
}
n = 0;
d = (1<<LOG_D)-1;
for(int i=0; i<N; i++){
if(vst[i]) continue;
if(dist[i] < d){
d = dist[i];
n = i;
}
}
}
void make_ans(){
vst[n] = true;
calc();
int n2 = n, d2 = d;
for(int i=0; i<LOG_N; i++){
SendB(n2%2); n2/=2;
}
for(int i=0; i<LOG_D; i++){
SendB(d2%2); d2/=2;
}
cnt = 0;
}
}
void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
::N = N;
for(int i=0; i<B; i++){
gp[S[i]].pb({T[i], D[i]});
gp[T[i]].pb({S[i], D[i]});
}
vst[0] = true;
for(int i=1; i<N; i++) dist[i] = (1<<LOG_D)-1;
calc();
int n2 = n, d2 = d;
for(int i=0; i<LOG_N; i++){
SendB(n2%2); n2/=2;
}
for(int i=0; i<LOG_D; i++){
SendB(d2%2); d2/=2;
}
cnt = 0;
}
void ReceiveB(bool y) {
if(cnt==0){
if(y==1){
make_ans();
}else{
n = d = 0;
cnt++;
}
return;
}
if(cnt<=LOG_N){
n = n*2 + y;
}else if(cnt<=LOG_D){
d = d*2 + y;
}
cnt++;
if(cnt==LOG_D+1){
make_ans();
}
}
Compilation message
Azer.cpp: In function 'void {anonymous}::calc()':
Azer.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[n].size(); i++){
~^~~~~~~~~~~~~
Baijan.cpp: In function 'void {anonymous}::calc()':
Baijan.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[n].size(); i++){
~^~~~~~~~~~~~~
Baijan.cpp: At global scope:
Baijan.cpp:36:10: warning: '{anonymous}::finish' defined but not used [-Wunused-variable]
bool finish = false;
^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
37 ms |
940 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
976 KB |
Output is correct |
2 |
Runtime error |
16 ms |
1072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
57 ms |
800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
91 ms |
948 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
91 ms |
948 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
91 ms |
948 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
37 ms |
940 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |