| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1179554 | PlayVoltz | Two Transportations (JOI19_transportations) | C++20 | 0 ms | 0 KiB |
#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
namespace{
int counter=0, val=0, phase=0, tempval, prev;
vector<int> dist, done, notdone;
vector<bool> del;
vector<deque<pii> > graph;
}
void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){
done.clear();
dist.clear();
graph.clear();
del.clear();
del.resize(n, 0);
done.resize(1, 0);
dist.resize(n, INT_MAX/2);
graph.resize(n);
dist[0]=counter=val=phase=prev=0;
del[0]=1;
for (int i=1; i<n; ++i)notdone.pb(i);
for (int i=0; i<a; ++i){
graph[u[i]].pb(mp(c[i], v[i]));
graph[v[i]].pb(mp(c[i], u[i]));
}
for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
}
void ReceiveA(bool x){
++counter;
val=val*2+x;
if (!phase&&counter==9){
int dj=INT_MAX/2, best;
for (auto node:done){
while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
if (graph[node].empty())continue;
if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
}
if (dj-prev<val){
SendA(0);
dist[best]=dj;
prev=dj;
done.pb(best);
del[best]=1;
int id=0;
for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
notdone.erase(find(notdone.begin(), notdone.end(), best));
for (int i=(int)log2(notdone.size()+1); i>=0; --i)SendA((1<<i)&id);
for (int i=8; i>=0; --i)SendA((1<<i)&(dj-prev));
}
else{
SendA(1);
phase=1;
}
counter=val=0;
}
if (phase==1&&counter==(int)log2(notdone.size())+1){
tempval=val;
phase=2;
counter=val=0;
}
if (phase==2&&counter==9){
int best=notdone[tempval];
dist[best]=val+prev;
prev+=val;
done.pb(best);
del[best]=1;
notdone.erase(find(notdone.begin(), notdone.end(), best));
phase=counter=val=0;
}
}
vector<int> Answer(){
return dist;
}
#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
namespace{
int counter=0, val=0, phase=0, tempval, dj=INT_MAX/2, best;
vector<int> dist, done, notdone;
vector<bool> del;
vector<deque<pii> > graph;
void sendover(){
if (notdone.empty())return;
prev=dj=INT_MAX/2;
for (auto node:done){
while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
if (graph[node].empty())continue;
if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
}
for (int i=8; i>=0; --i)SendB((1<<i)&(dj-prev));
}
}
void InitB(int n, int a, vector<int> u, vector<int> v, vector<int> c){
done.clear();
dist.clear();
graph.clear();
del.clear();
del.resize(n, 0);
done.resize(1, 0);
dist.resize(n, INT_MAX/2);
graph.resize(n);
dist[0]=counter=val=phase=prev=0;
del[0]=1;
for (int i=1; i<n; ++i)notdone.pb(i);
for (int i=0; i<a; ++i){
graph[u[i]].pb(mp(c[i], v[i]));
graph[v[i]].pb(mp(c[i], u[i]));
}
for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
sendover();
}
void ReceiveB(bool x){
++counter;
val=val*2+x;
if (!phase){
if (val){
dist[best]=dj;
prev=dj;
done.pb(best);
del[best]=1;
int id=0;
for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
notdone.erase(find(notdone.begin(), notdone.end(), best));
for (int i=log2(notdone.size()+1); i>=0; --i)SendB((1<<i)&id);
for (int i=8; i>=0; --i)SendB((1<<i)&(dj-prev));
sendover();
}
else phase=1;
val=counter=0;
}
if (phase==1&&counter==(int)log2(notdone.size())+1){
tempval=val;
phase=2;
counter=val=0;
}
if (phase==2&&counter==9){
int best=notdone[tempval];
dist[best]=val+prev;
prev+=val;
done.pb(best);
del[best]=1;
notdone.erase(find(notdone.begin(), notdone.end(), best));
phase=counter=val=0;
sendover();
}
}