Submission #290423

#TimeUsernameProblemLanguageResultExecution timeMemory
290423TadijaSebezTwo Transportations (JOI19_transportations)C++14
100 / 100
1890 ms85976 KiB
#include "Azer.h" #include <bits/stdc++.h> using namespace std; #define vi vector<int> #define pii pair<int,int> #define pb push_back namespace{ const int N=2050; const int L=9; const int inf=(1<<L)-1; vector<pii> E[N]; int dist[N],n; bool was[N]; void Upd(int x){ was[x]=1; for(auto e:E[x]){ int v,w;tie(v,w)=e; if(!was[v]){ dist[v]=min(dist[v],dist[x]+w); } } } int cnt,X,Y,node,D; int w; void Send(){ Y=1e9; bool ok=0; for(int i=0;i<n;i++)if(!was[i]){ ok=1; if(Y>dist[i]){ Y=dist[i]; node=i; } } if(!ok)return; Y-=D; Y=min(Y,inf); for(int i=L-1;~i;i--)SendA(Y>>i&1); w=1; } } void InitA(int n,int a,vi u,vi v,vi w){ ::n=n; for(int i=0;i<a;i++)E[u[i]].pb({v[i],w[i]}),E[v[i]].pb({u[i],w[i]}); for(int i=1;i<n;i++)dist[i]=1e9; D=0; Upd(0); Send(); } void ReceiveA(bool x){ X=X*2+x; cnt++; if(w==1){ if(cnt==L){ if(Y<=X){ for(int i=10;~i;i--)SendA(node>>i&1); D+=Y; Upd(node); Send(); cnt=0; X=0; }else{ D+=X; w=2; cnt=0; X=0; } } }else if(w==2){ if(cnt==11){ dist[X]=D; Upd(X); Send(); cnt=0; X=0; } } } vi Answer(){ vi ans; for(int i=0;i<n;i++)ans.pb(dist[i]); return ans; }
#include "Baijan.h" #include <bits/stdc++.h> using namespace std; #define vi vector<int> #define pii pair<int,int> #define pb push_back namespace{ const int N=2050; const int L=9; const int inf=(1<<L)-1; vector<pii> E[N]; int dist[N],n; bool was[N]; void Upd(int x){ was[x]=1; for(auto e:E[x]){ int v,w;tie(v,w)=e; if(!was[v]){ dist[v]=min(dist[v],dist[x]+w); } } } int cnt,X,Y,node,D; int w; void Send(){ Y=1e9; bool ok=0; for(int i=0;i<n;i++)if(!was[i]){ ok=1; if(Y>dist[i]){ Y=dist[i]; node=i; } } if(!ok)return; Y-=D; Y=min(Y,inf); for(int i=L-1;~i;i--)SendB(Y>>i&1); w=1; } } void InitB(int n,int b,vi u,vi v,vi w){ ::n=n; for(int i=0;i<b;i++)E[u[i]].pb({v[i],w[i]}),E[v[i]].pb({u[i],w[i]}); for(int i=1;i<n;i++)dist[i]=1e9; D=0; Upd(0); Send(); } void ReceiveB(bool y){ X=X*2+y; cnt++; if(w==1){ if(cnt==L){ if(Y<X){ for(int i=10;~i;i--)SendB(node>>i&1); D+=Y; Upd(node); Send(); cnt=0; X=0; }else{ D+=X; w=2; cnt=0; X=0; } } }else if(w==2){ if(cnt==11){ dist[X]=D; Upd(X); Send(); cnt=0; X=0; } } }
#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...