Submission #1227791

#TimeUsernameProblemLanguageResultExecution timeMemory
1227791MarwenElarbiTwo Transportations (JOI19_transportations)C++17
0 / 100
5963 ms13460 KiB
#include "Azer.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second namespace { int n_a; int lst_a=0; int dis_a[2500]; int j_a=0; int node_a=0; set<int> st_a; int d_a=0; vector<pair<int,int>> adj_a[2500]; void senda(pair<int,int> x){ if(x.fi>=1e8){ for (int i = 0; i < 11; ++i) { SendA(true); } for (int i = 0; i < 9; ++i) { SendA(true); } }else{ int u=x.se; int d=x.fi; for (int i = 0; i < 11; ++i) { SendA((1<<i)&u); } for (int i = 0; i < 9; ++i) { SendA((1<<i)&d); } } } } // namespace void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C) { n_a = N; for (int i = 0; i < N; ++i) { dis_a[i]=1e9; } for (int i = 0; i < A; ++i) { adj_a[U[i]].push_back({V[i],C[i]}); adj_a[V[i]].push_back({U[i],C[i]}); } dis_a[0]=0; st_a.insert(0); senda({0,0}); } void ReceiveA(bool x) { if(0<=j_a&&j_a<11){ node_a+=(x<<j_a); }else if(11<=j_a&&j_a<20){ d_a+=(x<<(j_a-11)); } j_a++; if(j_a==20){ //cout << "A" << " "<<node_a<<" "<<d_a<<endl; j_a=0; d_a+=lst_a; int cur_dis[n_a]; for (int i = 0; i < n_a; ++i) cur_dis[i]=1e9; if(node_a<1400&&!st_a.count(node_a)) cur_dis[node_a]=d_a; for(auto u:st_a){ for(auto i:adj_a[u]){ if(st_a.count(i.fi)) continue; cur_dis[i.fi]=min(cur_dis[i.fi],i.se+dis_a[u]); } } pair<int,int> res={1e9,1e9}; for (int i = 0; i < n_a; ++i){ //cout << (cur_dis[i]==1e9 ? -2 : cur_dis[i]) <<" "; if(cur_dis[i]==1e9) continue; res=min(res,make_pair(cur_dis[i],i)); }//cout <<endl; if(res.se<1e8) dis_a[res.se]=res.fi; if(res.se<1e8) st_a.insert(res.se); //for(int i=0;i<n_a;i++) cout <<(dis_a[i]==1e9 ? -1 :dis_a[i])<<" "; // cout <<endl; //cout <<res.fi-lst_a<<endl; senda({res.fi-lst_a,res.se}); lst_a=res.fi; node_a=0; d_a=0; } } std::vector<int> Answer() { std::vector<int> ans(n_a); for (int k = 0; k < n_a; ++k) { ans[k] = dis_a[k]; } return ans; }
#include "Baijan.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second namespace { int n_b; int j_b=0; int cnt=0; int lst_b=0; int node_b=0; int d_b=0; vector<pair<int,int>> adj_b[2500]; int dis_b[2500]; set<int> st_b; void sendb(pair<int,int> x){ if(x.se>=1e8){ for (int i = 0; i < 11; ++i) { SendB(true); } for (int i = 0; i < 9; ++i) { SendB(true); } }else{ int u=x.se; int d=x.fi; for (int i = 0; i < 11; ++i) { SendB((1<<i)&u); } for (int i = 0; i < 9; ++i) { SendB((1<<i)&d); } } } } // namespace void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D) { n_b=N; for (int i = 0; i < B; ++i) { adj_b[S[i]].push_back({T[i],D[i]}); adj_b[T[i]].push_back({S[i],D[i]}); } for (int i = 0; i < N; ++i) { dis_b[i]=1e9; } } void ReceiveB(bool y) { if(0<=j_b&&j_b<11){ node_b+=(y<<j_b); }else if(11<=j_b&&j_b<20){ d_b+=(y<<(j_b-11)); } j_b++; cnt+=2; if(cnt==57800) return; if(j_b==20){ //cout << "B" << " "<<node_b<<" "<<d_b<<endl; j_b=0; d_b+=lst_b; lst_b=d_b; if(node_b<1400){ st_b.insert(node_b); dis_b[node_b]=d_b; } //for(auto u:st_b) cout <<u<<" "; // cout <<endl; int cur_dis[n_b]; for (int i = 0; i < n_b; ++i) cur_dis[i]=1e9; for(auto u:st_b){ for(auto i:adj_b[u]){ if(st_b.count(i.fi)) continue; cur_dis[i.fi]=min(cur_dis[i.fi],i.se+dis_b[u]); } } pair<int,int> res={1e9,1e9}; for (int i = 0; i < n_b; ++i){ //cout <<(cur_dis[i]==1e9 ? -1 : cur_dis[i])<<" "; if(cur_dis[i]==1e9) continue; if(res.fi>cur_dis[i]){ res=min(res,make_pair(cur_dis[i],i)); } }//cout <<endl; //cout <<res.fi-lst_b<<endl; sendb({res.fi-lst_b,res.se}); d_b=0; node_b=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...