Submission #126695

#TimeUsernameProblemLanguageResultExecution timeMemory
126695dndhkTwo Transportations (JOI19_transportations)C++14
62 / 100
2041 ms85416 KiB
#include "Azer.h" #include <bits/stdc++.h> #define pb push_back #define all(v) ((v).begin(), (v).end()) #define sortv(v) sort(all(v)) #define sz(v) ((int)(v).size()) #define uniqv(v) (v).erase(unique(all(v)), (v).end()) #define umax(a, b) (a)=max((a), (b)) #define umin(a, b) (a)=min((a), (b)) #define FOR(i,a,b) for(int i = (a); i <= (b); i++) #define rep(i,n) FOR(i,1,n) #define rep0(i,n) FOR(i,0,(int)(n)-1) #define FI first #define SE second #define INF 2000000 #define INFLL 1000000000000000000LL using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAX_N = 2000; const int LOG_N = 11; const int LOG_D = 9; namespace { int N; vector<pii> gp[MAX_N+1]; int dist[MAX_N+1]; int vst[MAX_N+1]; int n=0, d=0, cnt=0; int mx; int n2=0, d2=0; bool finish = false; int two = 1; void calc(){ for(int i=0; i<gp[n].size(); i++){ if(dist[gp[n][i].first]>dist[n] + gp[n][i].second){ dist[gp[n][i].first] = dist[n] + gp[n][i].second; } } n2 = 0; d2 = INF+1; finish = true; for(int i=0; i<N; i++){ if(!vst[i]) finish = false; if(vst[i]) continue; if(dist[i] < d2){ d2 = dist[i]; n2 = i; } } } void make_ans(){ //cout<<n<<" "<<d<<" "<<mx<<endl<<endl; //cout<<n2<<" "<<d2<<endl<<endl; if(d<d2){ dist[n] = d; vst[n] = true; }else{ dist[n2] = d2; n = n2; d = d2; vst[n] = true; } calc(); if(finish){ Answer(); return; } //cout<<n<<" "<<d<<endl; //cout<<n<<" "<<d<<" "<<mx<<endl; for(int i=0; i<LOG_N; i++){ SendA((bool)(n%2)); n/=2; } d-=mx; d = min(d, (1<<LOG_D)-1); for(int i=0; i<LOG_D; i++){ SendA((bool)(d%2)); d/=2; } n = d = cnt = 0; two = 1; mx = 0; for(int i=0; i<N; i++){ if(!vst[i]) continue; mx = max(mx, dist[i]); } } } void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) { ::N = N; for (int i = 0; i < A; ++i) { gp[U[i]].pb({V[i], C[i]}); gp[V[i]].pb({U[i], C[i]}); } vst[0] = 1; dist[0] = 0; for(int i=1; i<N; i++){ dist[i] = INF; } mx = 0; for(int i=0; i<N; i++){ if(!vst[i]) continue; mx = max(mx, dist[i]); } calc(); // cout<<finish; if(finish){ Answer(); return; } } void ReceiveA(bool x) { if(cnt<LOG_N){ n += (int)x * two; two*=2; }else if(cnt < LOG_D+LOG_N){ d += (int)x * two; two*=2; } cnt++; if(cnt==LOG_N){ two = 1; } if(cnt==LOG_D+LOG_N){ d+=mx; make_ans(); } } vector<int> Answer() { vector<int> ans(N); for(int i=0; i<N; i++){ ans[i] = dist[i]; } return ans; }
#include "Baijan.h" #include <bits/stdc++.h> #define pb push_back #define all(v) ((v).begin(), (v).end()) #define sortv(v) sort(all(v)) #define sz(v) ((int)(v).size()) #define uniqv(v) (v).erase(unique(all(v)), (v).end()) #define umax(a, b) (a)=max((a), (b)) #define umin(a, b) (a)=min((a), (b)) #define FOR(i,a,b) for(int i = (a); i <= (b); i++) #define rep(i,n) FOR(i,1,n) #define rep0(i,n) FOR(i,0,(int)(n)-1) #define FI first #define SE second #define INF 2000000000 #define INFLL 1000000000000000000LL using namespace std; const int MAX_N = 2000; const int LOG_N = 11; const int LOG_D = 9; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; namespace { int N; vector<pii> gp[MAX_N+1]; int dist[MAX_N+1]; int vst[MAX_N+1]; int mx; int n=0, d=0, cnt=0; int two = 1; bool finish = false; void calc2(){ for(int i=0; i<gp[n].size(); i++){ if(dist[gp[n][i].first]>dist[n] + gp[n][i].second){ dist[gp[n][i].first] = dist[n] + gp[n][i].second; } } n = 0; d = INF+1; for(int i=0; i<N; i++){ if(vst[i]) continue; if(dist[i] < d){ d = dist[i]; n = i; } } } void make_ans2(){ vst[n] = true; dist[n] = d; //cout<<"*"<<n<<" "<<d<<" "<<mx<<endl<<endl; mx = 0; for(int i=0; i<N; i++){ if(!vst[i]) continue; mx = max(mx, dist[i]); } calc2(); //cout<<"*"<<n<<" "<<d<<" "<<mx<<endl; int n2 = n, d2 = d; for(int i=0; i<LOG_N; i++){ SendB((bool)(n2%2)); n2/=2; } d2-=mx; d2 = min(d2, (1<<LOG_D)-1); for(int i=0; i<LOG_D; i++){ SendB((bool)(d2%2)); d2/=2; } cnt = 0; } } void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) { if(N==1) return; ::N = N; for(int i=0; i<B; i++){ gp[S[i]].pb({T[i], D[i]}); gp[T[i]].pb({S[i], D[i]}); } vst[0] = true; for(int i=1; i<N; i++) dist[i] = INF; mx = 0; for(int i=0; i<N; i++){ if(!vst[i]) continue; mx = max(mx, dist[i]); } calc2(); int n2 = n, d2 = d; d2-=mx; //cout<<"*"<<n<<" "<<d<<" "<<endl; for(int i=0; i<LOG_N; i++){ SendB((bool)(n2%2)); n2/=2; } d2 = min(d2, (1<<LOG_D)-1); for(int i=0; i<LOG_D; i++){ SendB((bool)(d2%2)); d2/=2; } cnt = 0; } void ReceiveB(bool y) { if(cnt==0){ n = d = 0; two = 1; } //cout<<"#"<<cnt<<" "<<y<<endl; if(cnt<LOG_N){ n += (int)y*two; }else if(cnt<LOG_D+LOG_N){ d += (int)y*two; } two*=2; cnt++; if(cnt==LOG_N){ two = 1; } if(cnt==LOG_D+LOG_N){ d+=mx; make_ans2(); } }

Compilation message (stderr)

Azer.cpp: In function 'void {anonymous}::calc()':
Azer.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<gp[n].size(); i++){
                      ~^~~~~~~~~~~~~

Baijan.cpp: In function 'void {anonymous}::calc2()':
Baijan.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<gp[n].size(); i++){
                      ~^~~~~~~~~~~~~
Baijan.cpp: At global scope:
Baijan.cpp:38:10: warning: '{anonymous}::finish' defined but not used [-Wunused-variable]
     bool finish = false;
          ^~~~~~
#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...