제출 #1290727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290727		simona1230	Two Transportations (JOI19_transportations)	C++20	0 / 100	309 ms	1180 KiB

Azer

#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;
    q.push({0,0});
    d[0]=0;

    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=0;i<n;i++)
    {
        if(ver==-1&&!use[i]||ver!=-1&&d[ver]>d[i]&&!use[i])
            ver=i;
    }
    //cout<<ver<<" ---- "<<d[ver]<<endl;

    if(ver==-1)
    {
        Answer();
    }
    else
    {
        for(int i=0;i<10;i++)
            if((1<<i)&ver)SendA(1);
            else SendA(0);
        for(int i=0;i<19;i++)
            if((1<<i)&d[ver])SendA(1);
            else SendA(0);
            use[ver]=1;
    }
}

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-10));
        v[0].push_back({ver,dist});
        sendshortest();
        b.clear();

        //cout<<ver<<" > "<<dist<<endl;
    }
}

std::vector<int> Answer()
{
    vector<int> ans;
    for(int i=0;i<n;i++)
        ans.push_back(d[i]);
    return ans;
}

Baijan

#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;
    q.push({0,0});
    d1[0]=0;

    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=0; 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)SendB(1);
        else SendB(0);
    for(int i=0; i<19; i++)
        if((1<<i)&d1[ver])SendB(1);
        else SendB(0);
        use1[ver]=1;
}


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])
            {
                //cout<<"! "<<i<<endl;
                dist+=(1<<(i-10));
            }
        v1[0].push_back({ver,dist});
        sendshortest1();
        b1.clear();
        //cout<<ver<<" < "<<dist<<endl;
    }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16