Submission #389663

#	Time	Username	Problem	Language	Result	Execution time	Memory
389663		denkendoemeer	Two Transportations (JOI19_transportations)	C++14	100 / 100	938 ms	48844 KiB

Azer

#include<bits/stdc++.h>
#include "Azer.h"
#define inf 1e9
using namespace std;
namespace {
int n,cnt1,cnt2,nr,dist1,dist2;
bool ok;
vector<pair<int,int>>*g;
vector<int>dist;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
void update(int nod)
{
    for(auto it:g[nod]){
        if (dist[nod]+it.second<-dist[it.first]){
            dist[it.first]=-(dist[nod]+it.second);
            pq.push(make_pair(dist[nod]+it.second,it.first));
        }
    }
}
void query()
{
    int i;
    if (cnt1==0)
        return ;
    cnt1--;
    while(1){
        if (pq.empty()){
            dist2=511;
            for(i=8;i>=0;i--)
                SendA((dist2>>i)&1);
            return ;
        }
        pair<int,int>aux=pq.top();
        if (aux.first+dist[aux.second]==0){
            dist2=aux.first-dist1;
            for(i=8;i>=0;i--)
                SendA((dist2>>i)&1);
                return ;
        }
        pq.pop();
    }
}
}
void InitA(int N,int a,vector<int>u,vector<int>v,vector<int>c)
{
    n=N;
    g=new vector<pair<int,int>>[n];
    int i;
    for(i=0;i<a;i++){
        g[u[i]].push_back(make_pair(v[i],c[i]));
        g[v[i]].push_back(make_pair(u[i],c[i]));
    }
    dist.push_back(0);
    for(i=1;i<n;i++)
        dist.push_back(-inf);
    cnt1=n-1;
    dist1=0;
    update(0);
    query();
    ok=0;
    cnt2=0;
    nr=0;
}
void ReceiveA(bool x)
{
    int i;
    nr*=2;
    nr+=x;
    if (ok){
        cnt2++;
        if (cnt2==11){
            dist1+=dist2;
            dist[nr]=dist1;
            update(nr);
            query();
            ok=0;
            cnt2=0;
            nr=0;
        }
    }
    else{
        cnt2++;
        if (cnt2==9){
            if (nr>=dist2){
                int aux=pq.top().second;
                for(i=10;i>=0;i--)
                    SendA((aux>>i)&1);
                dist1+=dist2;
                dist[aux]=dist1;
                update(aux);
                query();
            }
            else{
                dist2=nr;
                ok=1;
            }
            cnt2=0;
            nr=0;
        }
    }
}
std::vector<int> Answer()
{
    return dist;
}

Baijan

#include<bits/stdc++.h>
#define inf 1e9
#include "Baijan.h"
using namespace std;
namespace {
int n,cnt1,cnt2,nr,dist1,dist2;
bool ok;
vector<pair<int,int>>*g;
vector<int>dist;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
void update(int nod)
{
    for(auto it:g[nod]){
        if (dist[nod]+it.second<-dist[it.first]){
            dist[it.first]=-(dist[nod]+it.second);
            pq.push(make_pair(dist[nod]+it.second,it.first));
        }
    }
}
void query()
{
    int i;
    if (cnt1==0)
        return ;
    cnt1--;
    while(1){
        if (pq.empty()){
            dist2=511;
            for(i=8;i>=0;i--)
                SendB((dist2>>i)&1);
            return ;
        }
        pair<int,int>aux=pq.top();
        if (aux.first+dist[aux.second]==0){
            dist2=aux.first-dist1;
            for(i=8;i>=0;i--)
                SendB((dist2>>i)&1);
            return ;
        }
        pq.pop();
    }
}
}
void InitB(int N,int b,vector<int>s,vector<int>t,vector<int>d)
{
    n=N;
    int i;
    g=new vector<pair<int, int>>[n];
    for(i=0;i<b;i++){
        g[s[i]].push_back(make_pair(t[i],d[i]));
        g[t[i]].push_back(make_pair(s[i],d[i]));
    }
    dist.push_back(0);
    for(i=1;i<N;i++)
        dist.push_back(-inf);
    cnt1=n-1;
    dist1=0;
    update(0);
    query();
    ok=0;
    cnt2=0;
    nr=0;
}
void ReceiveB(bool y)
{
    int i;
    nr*=2;
    nr+=y;
    if (ok){
        ++cnt2;
        if (cnt2==11){
            dist1+=dist2;
            dist[nr]=dist1;
            update(nr);
            query();
            ok=0;
            cnt2=0;
            nr=0;
        }
    }
    else{
        ++cnt2;
        if (cnt2==9){
            if (nr>dist2){
                int aux=pq.top().second;
                for(i=10;i>=0;i--)
                    SendB((aux>>i)&1);
                dist1+=dist2;
                dist[aux]=dist1;
                update(aux);
                query();
            }
            else{
                dist2=nr;
                ok=1;
            }
            cnt2=0;
            nr=0;
        }
    }
}

Compilation message (stderr)

Azer.cpp: In function 'void {anonymous}::query()':
Azer.cpp:36:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |             for(i=8;i>=0;i--)
      |             ^~~
Azer.cpp:38:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   38 |                 return ;
      |                 ^~~~~~

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