oj.uz

Submission #473176

# Submission time Handle Problem Language Result Execution time Memory
473176 2021-09-15T09:47:52 Z jk410 Two Transportations (JOI19_transportations) C++17
38 / 100
 794 ms 35364 KB 
#include "Azer.h"
#include <iostream>
#include <vector>
using namespace std;
namespace {
    struct edge{
        int v,cost;
    };
    const int INF=1e9,cnt_v=10,cnt_cost=19;
    int N,tmp_v,cnt_query,cnt_receive,v_receive,cost_receive;
    bool flag;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    void my_sendA(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendA(x&(1<<i));
    }
    int get_closest(){
        int v=-1;
        for (int i=0; i<N; i++){
            if (Used[i])
                continue;
            if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
                v=i;
        }
        return v;
    }
    void update_edge(int v){
        for (edge i:Edge[v])
            Dist[i.v]=min(Dist[i.v],Dist[v]+i.cost);
    }
    void send_closest(int v){
        my_sendA(cnt_v,v);
        if (v!=-1)
            my_sendA(cnt_cost,Dist[v]);
        else
            my_sendA(cnt_cost,0);
    }
}
void ReceiveA(bool x){
    if (!flag){
        v_receive+=x*(1<<cnt_receive);
        cnt_receive++;
    }
    else{
        cost_receive+=x*(1<<cnt_receive);
        cnt_receive++;
    }
    if (!flag&&cnt_receive==cnt_v){
        flag=true;
        cnt_receive=0;
    }
    if (flag&&cnt_receive==cnt_cost){
        flag=false;
        Dist[v_receive]=min(Dist[v_receive],cost_receive);
        Used[v_receive]=true;
        update_edge(v_receive);
        cnt_query++;
        tmp_v=get_closest();
        if (cnt_query<N-1)
            send_closest(tmp_v);
        v_receive=cost_receive=cnt_receive=0;
    }
}
void InitA(int n,int a,vector<int> u,vector<int> v,vector<int> c){
    N=n;
    cnt_query=cnt_receive=v_receive=cost_receive=0;
    flag=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    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]});
    }
    for (int i=0; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    Dist[0]=0;
    Used[0]=true;
    update_edge(0);
    tmp_v=get_closest();
    if (N>1)
        send_closest(tmp_v);
}
vector<int> Answer(){
    return Dist;
}

#include "Baijan.h"
#include <iostream>
#include <vector>
using namespace std;
namespace {
    struct edge{
        int v,cost;
    };
    const int INF=1e9,cnt_v=10,cnt_cost=19;
    int N,tmp_v,cnt_receive,v_receive,cost_receive;
    bool flag;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    void my_sendB(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendB(x&(1<<i));
    }
    int get_closest(){
        int v=-1;
        for (int i=0; i<N; i++){
            if (Used[i])
                continue;
            if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
                v=i;
        }
        return v;
    }
    void update_edge(int v){
        for (edge i:Edge[v])
            Dist[i.v]=min(Dist[i.v],Dist[v]+i.cost);
    }
    void send_closest(int v){
        my_sendB(cnt_v,v);
        my_sendB(cnt_cost,Dist[v]);
    }
}
void ReceiveB(bool y){
    if (!flag){
        v_receive+=y*(1<<cnt_receive);
        cnt_receive++;
    }
    else{
        cost_receive+=y*(1<<cnt_receive);
        cnt_receive++;
    }
    if (!flag&&cnt_receive==cnt_v){
        if (v_receive==(1<<cnt_v)-1)
            v_receive=-1;
        flag=true;
        cnt_receive=0;
    }
    if (flag&&cnt_receive==cnt_cost){
        flag=false;
        if (tmp_v==-1||v_receive!=-1&&Dist[tmp_v]>cost_receive){
            tmp_v=v_receive;
            Dist[tmp_v]=cost_receive;
        }
        Used[tmp_v]=true;
        update_edge(tmp_v);
        send_closest(tmp_v);
        tmp_v=get_closest();
        v_receive=cost_receive=cnt_receive=0;
    }
}
void InitB(int n,int b,vector<int> s,vector<int> t,vector<int> d){
    N=n;
    cnt_receive=v_receive=cost_receive=0;
    flag=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    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]});
    }
    for (int i=0; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    Dist[0]=0;
    Used[0]=true;
    update_edge(0);
    tmp_v=get_closest();
}

Compilation message

Azer.cpp: In function 'int {anonymous}::get_closest()':
Azer.cpp:24:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |             if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
      |                 ~~~~~^~~~~~~~~~~~~~

Baijan.cpp: In function 'int {anonymous}::get_closest()':
Baijan.cpp:24:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |             if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
      |                 ~~~~~^~~~~~~~~~~~~~
Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:55:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |         if (tmp_v==-1||v_receive!=-1&&Dist[tmp_v]>cost_receive){
      |                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 325 ms 328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 247 ms 320 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 290 ms 320 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 644 KB Output is correct
2 Correct 453 ms 608 KB Output is correct
3 Correct 528 ms 13272 KB Output is correct
4 Correct 539 ms 672 KB Output is correct
5 Correct 590 ms 9928 KB Output is correct
6 Correct 590 ms 652 KB Output is correct
7 Correct 326 ms 680 KB Output is correct
8 Correct 470 ms 684 KB Output is correct
9 Correct 711 ms 18184 KB Output is correct
10 Correct 687 ms 18088 KB Output is correct
11 Correct 794 ms 35364 KB Output is correct
12 Correct 709 ms 30656 KB Output is correct
13 Correct 540 ms 640 KB Output is correct
14 Correct 0 ms 384 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 644 KB Output is correct
2 Correct 453 ms 608 KB Output is correct
3 Correct 528 ms 13272 KB Output is correct
4 Correct 539 ms 672 KB Output is correct
5 Correct 590 ms 9928 KB Output is correct
6 Correct 590 ms 652 KB Output is correct
7 Correct 326 ms 680 KB Output is correct
8 Correct 470 ms 684 KB Output is correct
9 Correct 711 ms 18184 KB Output is correct
10 Correct 687 ms 18088 KB Output is correct
11 Correct 794 ms 35364 KB Output is correct
12 Correct 709 ms 30656 KB Output is correct
13 Correct 540 ms 640 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Incorrect 200 ms 320 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 644 KB Output is correct
2 Correct 453 ms 608 KB Output is correct
3 Correct 528 ms 13272 KB Output is correct
4 Correct 539 ms 672 KB Output is correct
5 Correct 590 ms 9928 KB Output is correct
6 Correct 590 ms 652 KB Output is correct
7 Correct 326 ms 680 KB Output is correct
8 Correct 470 ms 684 KB Output is correct
9 Correct 711 ms 18184 KB Output is correct
10 Correct 687 ms 18088 KB Output is correct
11 Correct 794 ms 35364 KB Output is correct
12 Correct 709 ms 30656 KB Output is correct
13 Correct 540 ms 640 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Incorrect 200 ms 320 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 325 ms 328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -