Submission #1066381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066381		urd05	Two Transportations (JOI19_transportations)	C++17	100 / 100	659 ms	49036 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> P;
 
namespace A {
 
int n;
int ca=0;
bool vis[2005];
vector<P> adj[2005];
priority_queue<P,vector<P>,greater<P>> pq;
int nowd=0;
int got=0;
int prd=0;
int cnt=0;
int dist[2005];
const int INF=1e6;
 
}  // namespace
 
typedef pair<int,int> P;
 
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    A::n=N;
    for(int i=0;i<A;i++) {
        A::adj[U[i]].push_back(P(V[i],C[i]));
        A::adj[V[i]].push_back(P(U[i],C[i]));
    }
    A::dist[0]=0;
    for(int i=1;i<A::n;i++) {
        A::dist[i]=A::INF;
A::pq.push(P(A::dist[i],i));
    }
    A::pq.push(P(0,0));
    A::nowd=0;
    SendA(0);
}
 
void ReceiveA(bool x) {
//printf(".%d %d\n",A::ca,x);
    if (A::ca==8) {
        if (x) {
            A::got+=(1<<(A::ca));
        }
        A::cnt++;
        if (A::nowd<=A::got) {
            int now=A::pq.top().second;
            for(int i=0;i<11;i++) {
                if (now&(1<<i)) {
                    SendA(1);
                }
                else {
                    SendA(0);
                }
            }
            if (A::cnt==A::n) {
                return;
            }
            A::ca=0;
            A::pq.pop();
            A::vis[now]=true;
            for(int i=0;i<A::adj[now].size();i++) {
                int nt=A::adj[now][i].first;
                int d=A::adj[now][i].second;
                if (A::dist[nt]>A::dist[now]+d) {
                    A::dist[nt]=A::dist[now]+d;
                    A::pq.push(P(A::dist[nt],nt));
                }
            }
            A::prd=A::dist[now];
            while (1) {
                now=A::pq.top().second;
                if (!A::vis[now]) {
                    break;
                }
                A::pq.pop();
            }
            A::nowd=A::pq.top().first-A::prd;
//printf("! %d %d\n",A::nowd,now);
if (A::nowd<=511)
            SendA(A::nowd&1);
else
	SendA(1);
            A::ca=0;
            A::got=0;
        }
        else {
            A::ca++;
            A::nowd=A::got;
A::got=0;
        }
    }
    else if (A::ca<8) {
        if (x) {
            A::got+=(1<<(A::ca));
        }
        A::ca++;
        if (A::nowd>511||(A::nowd&(1<<A::ca))) {
            SendA(1);
        }
        else {
            SendA(0);
        }
    }
    else if (A::ca>8) {
        if (x) {
            A::got+=(1<<(A::ca-9));
        }
        if (A::ca==19) {
            A::dist[A::got]=A::nowd+A::prd;
            int now=A::got;
            A::vis[now]=true;
            for(int i=0;i<A::adj[now].size();i++) {
                int nt=A::adj[now][i].first;
                int d=A::adj[now][i].second;
                if (A::dist[nt]>A::dist[now]+d) {
                    A::dist[nt]=A::dist[now]+d;
                    A::pq.push(P(A::dist[nt],nt));
                }
            }
            A::prd=A::dist[now];
            while (!A::pq.empty()) {
                now=A::pq.top().second;
                if (!A::vis[now]) {
                    break;
                }
                A::pq.pop();
            }
//printf("! %d\n",A::cnt);
            if (A::cnt==A::n) {
                return;
            }
            A::nowd=A::pq.top().first-A::prd;
//printf(".! %d %d\n",A::nowd,now);
if (A::nowd<=511) {
            SendA(A::nowd&1);
}
else {
SendA(1);
}
            A::ca=0;
            A::got=0;
        }
        else {
            A::ca++;
        }
    }
}
 
std::vector<int> Answer() {
  std::vector<int> ans(A::n);
  for (int k = 0; k < A::n; ++k) {
    ans[k] = A::dist[k];
  }
  return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;

namespace B {

int n;
int ca=0;
bool vis[2005];
vector<P> adj[2005];
priority_queue<P,vector<P>,greater<P>> pq;
int nowd=0;
int got=0;
int prd=0;
int cnt=0;
int dist[2005];
const int INF=1e6;

}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    B::n=N;
    for(int i=0;i<B;i++) {
        B::adj[S[i]].push_back(P(T[i],D[i]));
        B::adj[T[i]].push_back(P(S[i],D[i]));
    }
    B::dist[0]=0;
    for(int i=1;i<B::n;i++) {
        B::dist[i]=B::INF;
B::pq.push(P(B::dist[i],i));
    }
    B::pq.push(P(0,0));
    B::nowd=0;
}

void ReceiveB(bool y) {
//printf("..%d %d\n",B::ca,y);
    if (B::ca==8) {
        if (y) {
            B::got+=(1<<(B::ca));
        }
        if (B::nowd>511||(B::nowd&(1<<B::ca))) {
            SendB(1);
        }
        else {
            SendB(0);
        }
        B::cnt++;
        if (B::nowd<B::got) {
            int now=B::pq.top().second;
            for(int i=0;i<11;i++) {
                if (now&(1<<i)) {
                    SendB(1);
                }
                else {
                    SendB(0);
                }
            }
            if (B::cnt==B::n) {
                return;
            }
            B::ca=0;
            B::pq.pop();
            B::vis[now]=true;
            for(int i=0;i<B::adj[now].size();i++) {
                int nt=B::adj[now][i].first;
                int d=B::adj[now][i].second;
                if (B::dist[nt]>B::dist[now]+d) {
                    B::dist[nt]=B::dist[now]+d;
                    B::pq.push(P(B::dist[nt],nt));
                }
            }
            B::prd=B::dist[now];
            while (1) {
                now=B::pq.top().second;
                if (!B::vis[now]) {
                    break;
                }
                B::pq.pop();
            }
            B::nowd=B::pq.top().first-B::prd;
//printf("!! %d %d\n",B::nowd,now);
            B::ca=0;
            B::got=0;
        }
        else {
            B::ca++;
            B::nowd=B::got;
B::got=0;
        }
    }
    else if (B::ca<8) {
        if (y) {
            B::got+=(1<<(B::ca));
        }
        if (B::nowd>511||(B::nowd&(1<<B::ca))) {
            SendB(1);
        }
        else {
            SendB(0);
        }
B::ca++;
    }
    else if (B::ca>8) {
        if (y) {
            B::got+=(1<<(B::ca-9));
        }
        if (B::ca==19) {
            B::dist[B::got]=B::nowd+B::prd;
            int now=B::got;
            B::vis[now]=true;
            for(int i=0;i<B::adj[now].size();i++) {
                int nt=B::adj[now][i].first;
                int d=B::adj[now][i].second;
                if (B::dist[nt]>B::dist[now]+d) {
                    B::dist[nt]=B::dist[now]+d;
                    B::pq.push(P(B::dist[nt],nt));
                }
            }
//printf(".%d\n",now);
B::prd=B::dist[now];
            while (!B::pq.empty()) {
                now=B::pq.top().second;
                if (!B::vis[now]) {
                    break;
                }
                B::pq.pop();
            }
            if (B::cnt==B::n) {
                return;
            }
            B::nowd=B::pq.top().first-B::prd;
//printf(".!! %d %d\n",B::nowd,now);
            B::ca=0;
            B::got=0;
        }
        else {
            B::ca++;
        }
    }
}

Compilation message (stderr)

Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int i=0;i<A::adj[now].size();i++) {
      |                         ~^~~~~~~~~~~~~~~~~~~
Azer.cpp:116:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for(int i=0;i<A::adj[now].size();i++) {
      |                         ~^~~~~~~~~~~~~~~~~~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i=0;i<B::adj[now].size();i++) {
      |                         ~^~~~~~~~~~~~~~~~~~~
Baijan.cpp:115:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for(int i=0;i<B::adj[now].size();i++) {
      |                         ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16