oj.uz

Submission #123298

# Submission time Handle Problem Language Result Execution time Memory
123298 2019-07-01T06:21:06 Z 송준혁(#3022) Two Transportations (JOI19_transportations) C++14
0 / 100
 904 ms 25952 KB 
#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

static int N, M;
static vector<pii> adj[2020];
static vector<int> ans;
static int cnt, Bu, Bv, Bw, num, E;
static bool chk[2020], Bchk[2020];

static priority_queue<pii, vector<pii>, greater<pii>> PQ;

void InitA(int n, int A, vector<int> U, vector<int> V, vector<int> C){
    N = n, M = A;
    ans.resize(N);
    for (int i=0; i<M; i++){
        adj[U[i]].push_back(pii(V[i], C[i]));
        adj[V[i]].push_back(pii(U[i], C[i]));
    }
    PQ.push(pii(0, 0));
}

void ReceiveA(bool x){
    if (E == -1){
        if (x){
            if (cnt < 11) Bu |= (1 << cnt);
            else if (cnt < 22) Bv |= (1 << (cnt-11));
            else Bw |= (1 << (cnt-22));
        }
        cnt++;
        if (cnt >= 31){
            cnt = 0;
            adj[Bu].push_back(pii(Bv, Bw));
            Bchk[Bu] = Bchk[Bv] = true;
            Bu = Bv = Bw = 0;
            num--;
        }
        if (!num){
            E = 0;
            while (!PQ.empty()){
                pii T = PQ.top();
                PQ.pop();
                if (chk[T.second]) continue;
                if (!Bchk[T.second]){
                    PQ.push(T);
                    Bchk[T.second] = true;
                    for (int i=0; i<11; i++) SendA(T.second & (1<<i));
                    return;
                }
                chk[T.second] = true;
                ans[T.second] = T.first;
                for (pii v : adj[T.second]) PQ.push(pii(T.first+v.second, v.first));
            }
        }
    }
    else if (E < 11){
        if (x) num |= (1 << E);
        E++;
        if (E == 11) {
            E = -1;
            if (num == 0){
                E = 0;
                while (!PQ.empty()){
                    pii T = PQ.top();
                    PQ.pop();
                    if (chk[T.second]) continue;
                    if (!Bchk[T.second]){
                        PQ.push(T);
                        Bchk[T.second] = true;
                        for (int i=0; i<11; i++) SendA(T.second & (1<<i));
                        return;
                    }
                    chk[T.second] = true;
                    ans[T.second] = T.first;
                    for (pii v : adj[T.second]) PQ.push(pii(T.first+v.second, v.first));
                }
            }
        }
    }
}

vector<int> Answer() {
    return ans;
}

#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

static int N, M, num, st;
static bool chk[2020];
static vector<pii> adj[2020];

namespace {
struct Data{
    int u, v, w, d;
    bool operator<(const Data &r)const{
        return d > r.d;
    }
};
}
static vector<Data> O;
static priority_queue<Data> PQ;

void InitB(int n, int B, vector<int> U, vector<int> V, vector<int> C) {
    N = n, M = B;
    PQ.push((Data){0, 0, 0, 0});

    for (int i=0; i<M; i++) {
        adj[U[i]].push_back(pii(V[i], C[i]));
        adj[V[i]].push_back(pii(U[i], C[i]));
    }

    while (!PQ.empty()){
        Data T = PQ.top();
        PQ.pop();
        if (chk[T.v]) continue;
        chk[T.v] = true;
        if (T.w != 0) O.push_back(T);
        for (pii nx : adj[T.v]) PQ.push((Data){T.v, nx.first, nx.second, nx.second + T.d});
    }

    for (int i=0; i<11; i++) SendB(O.size() & (1<<i));
    for (Data T : O){
        for (int i=0; i<11; i++) SendB(T.u & (1<<i));
        for (int i=0; i<11; i++) SendB(T.v & (1<<i));
        for (int i=0; i<9; i++) SendB(T.w & (1<<i));
    }
    O.clear();
}

void ReceiveB(bool y){
    if (num < 11) if (y) st |= (1<<num);
    num++;
    if (num == 11){
        PQ.push((Data){0, st, 0, 0});
        while (!PQ.empty()){
            Data T = PQ.top();
            PQ.pop();
            if (chk[T.v]) continue;
            chk[T.v] = true;
            if (T.w != 0) O.push_back(T);
            for (pii nx : adj[T.v]) PQ.push((Data){T.v, nx.first, nx.second, nx.first + T.d});
        }

        for (int i=0; i<11; i++) SendB(O.size() & (1<<i));
        for (Data T : O){
            for (int i=0; i<11; i++) SendB(T.u & (1<<i));
            for (int i=0; i<11; i++) SendB(T.v & (1<<i));
            for (int i=0; i<9; i++) SendB(T.w & (1<<i));
        }
        O.clear();
        num=st=0;
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1344 KB Output is correct
2 Correct 904 ms 1576 KB Output is correct
3 Incorrect 840 ms 1768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 1480 KB Output is correct
2 Correct 6 ms 1216 KB Output is correct
3 Incorrect 10 ms 872 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 1352 KB Output is correct
2 Correct 422 ms 1352 KB Output is correct
3 Correct 732 ms 25952 KB Output is correct
4 Correct 530 ms 1560 KB Output is correct
5 Incorrect 790 ms 18752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 1352 KB Output is correct
2 Correct 422 ms 1352 KB Output is correct
3 Correct 732 ms 25952 KB Output is correct
4 Correct 530 ms 1560 KB Output is correct
5 Incorrect 790 ms 18752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 1352 KB Output is correct
2 Correct 422 ms 1352 KB Output is correct
3 Correct 732 ms 25952 KB Output is correct
4 Correct 530 ms 1560 KB Output is correct
5 Incorrect 790 ms 18752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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