Submission #1194025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194025		8pete8	Two Transportations (JOI19_transportations)	C++20	100 / 100	364 ms	49552 KiB

Azer

#include "Azer.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
namespace {

int n;
int variable_example[500000];
int count;
vector<pii>adj[2002];
priority_queue<pii,vector<pii>,greater<pii>>pq;
int dist[2002];
int mx=0;
int c=0,cx=1,val=0;
int c2=0,cx2=1,val2=0;
int need=0;
int found=1;
}

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]].pb({V[i],C[i]});
    adj[V[i]].pb({U[i],C[i]});
  }
  for(int i=0;i<n;i++)dist[i]=1e9;
  dist[0]=0;
  for(auto i:adj[0])pq.push({i.s,i.f});
}

void ReceiveA(bool x){
  if(found==n)return;
  if(need){
    if(x)val2+=cx2;
    c2++;
    cx2*=2;
    if(c2<11)return;
    dist[val2]=mx+val;
    found++;
    for(auto i:adj[val2])if(dist[i.f]>dist[val2]+i.s)pq.push({dist[val2]+i.s,i.f});
    mx+=val;
    need=0;
    c2=0;
    cx2=1;
    val2=0;
    c=0;
    cx=1;
    val=0;
    return;
  }
  if(x)val+=cx;
  c++;
  cx*=2;
  if(c<9)return;
  while(!pq.empty()&&dist[pq.top().s]<=pq.top().f)pq.pop();
  if(pq.empty()||pq.top().f-mx>val)need=1;
  if(need){
    for(int i=0;i<9;i++)SendA(1);
  }
  else{
    for(int i=0;i<9;i++)SendA(!!((pq.top().f-mx)&(1LL<<i)));
    for(int i=0;i<11;i++)SendA(!!(pq.top().s&(1LL<<i)));
    mx=pq.top().f;
    dist[pq.top().s]=pq.top().f;
    found++;
    for(auto i:adj[pq.top().s])if(dist[i.f]>pq.top().f+i.s)pq.push({pq.top().f+i.s,i.f});
    pq.pop();
    c=0;
    cx=1;
    val=0;
  }

}
vector<int> Answer() {
  vector<int> ans(n);
  for (int k = 0; k < n; ++k) {
    ans[k] = dist[k];
  }
  return ans;
}

Baijan

#include "Baijan.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
namespace {

int n;
int count;

bool FunctionExample(bool P) {
  return !P;
}
vector<pii>adj[2002];
priority_queue<pii,vector<pii>,greater<pii>>pq;
int dist[2002];
int c=0,cx=1,val=0;
int c2=0,cx2=1,val2=0,mx=0;
int need=0;
int found=1;

}  // namespace

void get(){
  if(found==n)return;
  while(!pq.empty()&&dist[pq.top().s]<=pq.top().f)pq.pop();
  if(pq.empty())for(int i=0;i<9;i++)SendB(1);
  else for(int i=0;i<9;i++)SendB(!!((pq.top().f-mx)&(1LL<<i)));
}

void InitB(int N, int B, vector<int> S, vector<int> T,vector<int> D) {
  n=N;
  for (int i = 0; i < B; ++i){
    adj[S[i]].pb({T[i],D[i]});
    adj[T[i]].pb({S[i],D[i]});
  }
  for(int i=0;i<n;i++)dist[i]=1e9;
  dist[0]=0;
  for(auto i:adj[0])pq.push({i.s,i.f});
  get();
}

void ReceiveB(bool y){
  if(found==n)return;
  if(need){
    if(y)val2+=cx2;
    c2++;
    cx2*=2;
    if(c2<11)return;
    dist[val2]=mx+val;
    found++;
    for(auto i:adj[val2])if(dist[i.f]>dist[val2]+i.s)pq.push({dist[val2]+i.s,i.f});
    mx+=val;
    need=0;
    c2=0;
    cx2=1;
    val2=0;
    c=0;
    cx=1;
    val=0;
    get();
    return;
  }
  if(y)val+=cx;
  c++;
  cx*=2;
  if(c<9)return;
  if(val>500){
    for(int i=0;i<11;i++)SendB(!!(pq.top().s&(1LL<<i)));
    dist[pq.top().s]=pq.top().f;
    for(auto i:adj[pq.top().s])if(dist[i.f]>pq.top().f+i.s)pq.push({pq.top().f+i.s,i.f});
    found++;
    mx=pq.top().f;
    pq.pop();
    c=0;
    cx=1;
    val=0;
    get();
    //we need to send them id
  }
  else{
    need=1;
    //they sending id
  }

}

• 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