oj.uz

Submission #475737

# Submission time Handle Problem Language Result Execution time Memory
475737 2021-09-23T23:33:07 Z jk410 Two Transportations (JOI19_transportations) C++17
6 / 100
 671 ms 10008 KB 
#include "Azer.h"
#include <vector>
#include <queue>
using namespace std;
namespace{
    struct edge{
        int v,cost;
        bool operator<(const edge &t)const{
            return cost>t.cost;
        }
    };
    const int INF=1e9,cnt_cost=9,cnt_v=11;
    int N,cnt,cnt_query,receive_cost,receive_v,cur_cost,sent_cost;
    edge closest;
    bool cur_mode;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    priority_queue<edge> Q;
    void my_send(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendA(x&(1<<i));
    }
    edge get_closest(){
        while (!Q.empty()){
            if (!Used[Q.top().v])
                return Q.top();
            Q.pop();
        }
        return {-1,-1};
    }
    void update_and_send(edge t){
        Dist[t.v]=t.cost;
        Used[t.v]=true;
        if (cnt_query==N-1)
            return;
        for (edge i:Edge[t.v]){
            if (Used[i.v])
                continue;
            Q.push({i.v,Dist[t.v]+i.cost});
        }
        closest=get_closest();
        if (closest.v==-1)
            my_send(cnt_cost,-1);
        else{
            my_send(cnt_cost,closest.cost-sent_cost);
            sent_cost=closest.cost;
        }
    }
}
void InitA(int n,int a,vector<int> u,vector<int> v,vector<int> c){
    N=n;
    cnt=cnt_query=receive_cost=receive_v=cur_cost=sent_cost=0;
    cur_mode=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    for (int i=0; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    for (int i=0; i<a; i++){
        Edge[u[i]].push_back({v[i],c[i]});
        Edge[v[i]].push_back({u[i],c[i]});
    }
    update_and_send({0,0});
}
void ReceiveA(bool x){
    if (!cur_mode&&cnt<cnt_cost){
        receive_cost+=x*(1<<cnt);
        cnt++;
    }
    if (cur_mode&&cnt<cnt_v){
        receive_v+=x*(1<<cnt);
        cnt++;
    }
    if (!cur_mode&&cnt==cnt_cost){
        cnt_query++;
        if (receive_cost!=(1<<cnt_cost)-1)
            cur_cost+=receive_cost;
        if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&cur_cost>closest.cost){
            Q.pop();
            cur_cost=closest.cost;
            my_send(cnt_v,closest.v);
            update_and_send(closest);
        }
        else{
            sent_cost=cur_cost;
            cur_mode=true;
        }
        cnt=receive_cost=0;
    }
    if (cur_mode&&cnt==cnt_v){
        update_and_send({receive_v,cur_cost});
        cnt=receive_v=0;
        cur_mode=false;
    }
}
vector<int> Answer(){
    return Dist;
}

#include "Baijan.h"
#include <vector>
#include <queue>
using namespace std;
namespace{
    struct edge{
        int v,cost;
        bool operator<(const edge &t)const{
            return cost>t.cost;
        }
    };
    const int INF=1e9,cnt_cost=9,cnt_v=11;
    int N,cnt,receive_cost,receive_v,cur_cost,sent_cost;
    edge closest;
    bool cur_mode;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    priority_queue<edge> Q;
    void my_send(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendB(x&(1<<i));
    }
    edge get_closest(){
        while (!Q.empty()){
            if (!Used[Q.top().v])
                return Q.top();
            Q.pop();
        }
        return {-1,-1};
    }
    void update_closest(edge t){
        Dist[t.v]=t.cost;
        Used[t.v]=true;
        for (edge i:Edge[t.v]){
            if (Used[i.v])
                continue;
            Q.push({i.v,Dist[t.v]+i.cost});
        }
    }
}
void InitB(int n,int b,vector<int> s,vector<int> t,vector<int> d){
    N=n;
    cnt=receive_cost=receive_v=cur_cost=sent_cost=0;
    cur_mode=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    for (int i=1; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    for (int i=0; i<b; i++){
        Edge[s[i]].push_back({t[i],d[i]});
        Edge[t[i]].push_back({s[i],d[i]});
    }
    update_closest({0,0});
}
void ReceiveB(bool y){
    if (!cur_mode&&cnt<cnt_cost){
        receive_cost+=y*(1<<cnt);
        cnt++;
    }
    if (cur_mode&&cnt<cnt_v){
        receive_v+=y*(1<<cnt);
        cnt++;
    }
    if (!cur_mode&&cnt==cnt_cost){
        if (receive_cost!=(1<<cnt_cost)-1)
            cur_cost+=receive_cost;
        closest=get_closest();
        if (closest.v==-1)
            my_send(cnt_cost,-1);
        else{
            my_send(cnt_cost,closest.cost-sent_cost);
            sent_cost=closest.cost;
        }
        if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&cur_cost>closest.cost){
            Q.pop();
            cur_cost=closest.cost;
            update_closest(closest);
            my_send(cnt_v,closest.v);
        }
        else{
            sent_cost=cur_cost;
            cur_mode=true;
        }
        cnt=receive_cost=0;
    }
    if (cur_mode&&cnt==cnt_v){
        update_closest({receive_v,cur_cost});
        cnt=receive_v=0;
        cur_mode=false;
    }
}

Compilation message

Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:81:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   81 |         if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&cur_cost>closest.cost){
      |                                            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:78:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |         if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&cur_cost>closest.cost){
      |                                            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 640 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 572 ms 768 KB Output is correct
4 Correct 671 ms 10008 KB Output is correct
5 Correct 32 ms 740 KB Output is correct
6 Correct 610 ms 2472 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 539 ms 716 KB Output is correct
3 Incorrect 6 ms 872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 640 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 572 ms 768 KB Output is correct
4 Correct 671 ms 10008 KB Output is correct
5 Correct 32 ms 740 KB Output is correct
6 Correct 610 ms 2472 KB Output is correct
7 Correct 1 ms 388 KB Output is correct
8 Correct 539 ms 716 KB Output is correct
9 Incorrect 6 ms 872 KB Output isn't correct
10 Halted 0 ms 0 KB -