| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1288406 | simona1230 | Two Transportations (JOI19_transportations) | C++20 | 0 ms | 0 KiB |
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int x,d;
edge(){}
edge(int _x,int _d)
{
x=_x;
d=_d;
}
bool operator<(const edge&e)const
{
return e.d<d;
}
};
int n;
vector<edge> v[2001];
int d[2001];
void dijkstra()
{
for(int i=0;i<n;i++)
d[i]=1e6;
priority_queue<edge> q;
while(q.size())
{
edge t=q.top();
q.pop();
if(d[t.x]>=t.d)
{
for(int i=0;i<v[t.x].size();i++)
{
edge nb=v[t.x][i];
if(d[nb.x]>nb.d+t.d)
{
d[nb.x]=nb.d+t.d;
q.push({nb.x,d[nb.x]});
}
}
}
}
}
int use[200001];
void sendshortest()
{
dijkstra();
int ver=-1;
for(int i=1;i<n;i++)
{
if(ver==-1&&!use[i]||ver!=-1&&d[ver]>d[i]&&!use[i])
ver=i;
}
if(ver==-1)
{
Answer();
}
else
{
use[ver]=1;
for(int i=0;i<10;i++)
if((1<<i)&ver)SendB((bool)(1));
else SendB((bool)(0));
for(int i=0;i<19;i++)
if((1<<i)&d[ver])SendB((bool)1);
else SendB((bool)0);
}
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C)
{
n=N;
for(int i=0;i<U.size();i++)
{
v[U[i]].push_back({V[i],C[i]});
v[V[i]].push_back({U[i],C[i]});
}
sendshortest();
}
vector<bool> b;
void ReceiveA(bool x)
{
b.push_back(x);
if(b.size()==29)
{
int ver=0;
int dist=0;
for(int i=0;i<10;i++)
if(b[i])ver+=(1<<i);
for(int i=10;i<29;i++)
if(b[i])dist+=(1<<i);
v[0].push_back({ver,dist});
sendshortest();
b.clear();
}
}
std::vector<int> Answer()
{
vector<int> ans;
for(int i=0;i<n;i++)
ans.push_back(d[i]);
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
struct edge1
{
int x,d;
edge1() {}
edge1(int _x,int _d)
{
x=_x;
d=_d;
}
bool operator<(const edge1&e)const
{
return e.d<d;
}
};
int n1;
vector<edge1> v1[2001];
int d1[2001];
void dijkstra1()
{
for(int i=0; i<n1; i++)
d1[i]=1e6;
priority_queue<edge1> q;
while(q.size())
{
edge1 t=q.top();
q.pop();
if(d1[t.x]>=t.d)
{
for(int i=0; i<v1[t.x].size(); i++)
{
edge1 nb=v1[t.x][i];
if(d1[nb.x]>nb.d+t.d)
{
d1[nb.x]=nb.d+t.d;
q.push({nb.x,d1[nb.x]});
}
}
}
}
}
int use1[200001];
void sendshortest1()
{
dijkstra1();
int ver=-1;
for(int i=1; i<n1; i++)
{
if(ver==-1&&!use1[i]||ver!=-1&&d1[ver]>d1[i]&&!use1[i])
ver=i;
}
for(int i=0; i<10; i++)
if((1<<i)&ver)SendA((bool)1);
else SendA((bool)0);
for(int i=0; i<19; i++)
if((1<<i)&d1[ver])SendA((bool)1);
else SendA((bool)0);
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D)
{
n1=N;
for(int i=0;i<S.size();i++)
{
v1[S[i]].push_back({T[i],D[i]});
v1[T[i]].push_back({S[i],D[i]});
}
}
vector<bool> b1;
void ReceiveB(bool x)
{
b1.push_back(x);
if(b1.size()==29)
{
int ver=0;
int dist=0;
for(int i=0;i<10;i++)
if(b1[i])ver+=(1<<i);
for(int i=10;i<29;i++)
if(b1[i])dist+=(1<<i);
v1[0].push_back({ver,dist});
sendshortest1();
use1[ver]=1;
b1.clear();
}
}