Submission #831828

#TimeUsernameProblemLanguageResultExecution timeMemory
831828NoName14159Two Transportations (JOI19_transportations)C++17
100 / 100
596 ms49400 KiB
#include "Azer.h" #include <stdlib.h> #include <cassert> #include <queue> #define MAXN 2007 #define MAXM 500007 #define vi std::vector<int> #define pii std::pair<int,int> #define vpii std::vector<pii> #define pqpii std::priority_queue<pii,vpii,std::greater<pii>> #define LOOP(I,X) for(int I=0;I<X;I++) #define pub push_back namespace{ enum Mode{ RE, // recommend edge DW, // determine winner SR, // send relax RX // relax }; Mode mode; bool winner; int n; int dis[MAXN]; bool visited[MAXN]={}; vpii e[MAXN]; pqpii pq; pii rec; int rec_other; int relax_w=0; int relax_v; bool buf[58007]; int buf_size=0; int buf_now=0; int t=0; int bits_next; //int cnt=0; int Read(int bits){ int ans=0; LOOP(i,bits){ ans<<=1; ans|=(int)buf[buf_now+i]; } buf_now+=bits; return ans; } void Send(int bits,int x){ LOOP(i,bits){ //cnt++; //assert(buf_size+cnt<=58000); SendA((bool)((x>>(bits-1-i))&1)); } } void Do(){ while(t<n-1){ if(mode==RE){ mode=DW; while(!pq.empty()){ pii x=pq.top(); if(!visited[x.second]){ break; } pq.pop(); } if(pq.empty()){ rec={511,-1}; }else{ rec=pq.top(); rec.first-=relax_w; } Send(9,rec.first); bits_next=9; return; } if(mode==DW){ mode=SR; rec_other=Read(9); if(rec.first<=rec_other){ winner=true; }else{ winner=false; } if(!winner){ bits_next=11; return; } } if(mode==SR){ mode=RX; if(winner){ Send(11,rec.second); relax_v=rec.second; relax_w+=rec.first; }else{ relax_v=Read(11); relax_w+=rec_other; } } if(mode==RX){ mode=RE; dis[relax_v]=relax_w; visited[relax_v]=true; for(pii x:e[relax_v]){ if(!visited[x.first]){ pq.push({relax_w+x.second,x.first}); } } t++; } } } } void InitA(int N,int A,vi U,vi V,vi C){ n=N; LOOP(i,A){ e[U[i]].pub({V[i],C[i]}); e[V[i]].pub({U[i],C[i]}); } dis[0]=0; visited[0]=true; for(pii x:e[0]){ pq.push({x.second,x.first}); } mode=RE; Do(); } void ReceiveA(bool x){ buf[buf_size]=x; buf_size++; if(buf_size-buf_now==bits_next){ Do(); } } vi Answer(){ vi ans; LOOP(i,n){ ans.pub(dis[i]); } return ans; }
#include "Baijan.h" #include <stdlib.h> #include <cassert> #include <queue> #define MAXN 2007 #define MAXM 500007 #define vi std::vector<int> #define pii std::pair<int,int> #define vpii std::vector<pii> #define pqpii std::priority_queue<pii,vpii,std::greater<pii>> #define LOOP(I,X) for(int I=0;I<X;I++) #define pub push_back namespace{ enum Mode{ RE, // recommend edge DW, // determine winner SR, // send relax RX // relax }; Mode mode; bool winner; int n; int dis[MAXN]; bool visited[MAXN]={}; vpii e[MAXN]; pqpii pq; pii rec; int rec_other; int relax_w=0; int relax_v; bool buf[58007]; int buf_size=0; int buf_now=0; int t=0; int bits_next; //int cnt=0; int Read(int bits){ int ans=0; LOOP(i,bits){ ans<<=1; ans|=(int)buf[buf_now+i]; } buf_now+=bits; return ans; } void Send(int bits,int x){ LOOP(i,bits){ //cnt++; //assert(buf_size+cnt<=58000); SendB((bool)((x>>(bits-1-i))&1)); } } void Do(){ while(t<n-1){ if(mode==RE){ mode=DW; while(!pq.empty()){ pii x=pq.top(); if(!visited[x.second]){ break; } pq.pop(); } if(pq.empty()){ rec={511,-1}; }else{ rec=pq.top(); rec.first-=relax_w; } Send(9,rec.first); bits_next=9; return; } if(mode==DW){ mode=SR; rec_other=Read(9); if(rec.first<rec_other){ winner=true; }else{ winner=false; } if(!winner){ bits_next=11; return; } } if(mode==SR){ mode=RX; if(winner){ Send(11,rec.second); relax_v=rec.second; relax_w+=rec.first; }else{ relax_v=Read(11); relax_w+=rec_other; } } if(mode==RX){ mode=RE; dis[relax_v]=relax_w; visited[relax_v]=true; for(pii x:e[relax_v]){ if(!visited[x.first]){ pq.push({relax_w+x.second,x.first}); } } t++; } } } } void InitB(int N,int B,vi S,vi T,vi D){ n=N; LOOP(i,B){ e[S[i]].pub({T[i],D[i]}); e[T[i]].pub({S[i],D[i]}); } dis[0]=0; visited[0]=true; for(pii x:e[0]){ pq.push({x.second,x.first}); } mode=RE; Do(); } void ReceiveB(bool x){ buf[buf_size]=x; buf_size++; if(buf_size-buf_now==bits_next){ Do(); } }
#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...