oj.uz

Submission #122746

# Submission time Handle Problem Language Result Execution time Memory
122746 2019-06-29T08:22:26 Z Plurm Two Transportations (JOI19_transportations) C++14
6 / 100
 1162 ms 23776 KB 
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    int N;
    const int INF = (1 << 28) - 1;
    int dist[2048];
    vector<tuple<int,int,int> > ev;
    bool upd[2048];
    bool relax(){
        bool chg = false;
        for(auto e : ev){
            int u,v,w;
            tie(u,v,w) = e;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                upd[v] = true;
                chg = true;
            }
        }
        return chg;
    }
    void updateval(){
        bool cont = false;
        for(int i = 0; i < N; i++){
            if(upd[i]){
                cont = true;
            }
        }
        if(!cont) return;
        vector<int> send;
        for(int i = 0; i < N; i++){
            if(upd[i]){
                send.push_back(dist[i]);
                SendA(true);
            }else{
                SendA(false);
            }
        }
        for(auto x : send){
            for(int j = 0; j < 28; j++){
                if(x & (1 << j)) SendA(true);
                else SendA(false);
            }
        }
    }
    vector<bool> cur;
    vector<int> dat;
    int popcount = 0;
}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V,
           vector<int> C) {
    ::N = N;
    for(int i = 0; i < N; i++) dist[i] = INF;
    dist[0] = 0;
    for(int i = 0; i < A; i++){
        ev.emplace_back(U[i], V[i], C[i]);
        ev.emplace_back(V[i], U[i], C[i]);
    }
}

void ReceiveA(bool x) {
    if(cur.size() < N){
        if(x) popcount++;
        cur.push_back(x);
    }else if(cur.size() - N < 28*popcount-1){
        cur.push_back(x);
    }else if(cur.size() - N == 28*popcount-1){
        cur.push_back(x);
        for(int i = N; i < cur.size(); i += 28){
            int s = 0;
            for(int j = 0; j < 28; j++){
                s += cur[i+j] ? 1 << j : 0;
            }
            dat.push_back(s);
        }
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(cur[i]){
                dist[i] = min(dist[i], dat[cnt]);
                cnt++;
            }
        }
        memset(upd, false, sizeof(upd));
        while(relax());
        cur.clear();
        dat.clear();
        popcount = 0;
        updateval();
    }
}

vector<int> Answer() {
    vector<int> ans;
    for(int i = 0; i < N; i++){
        ans.push_back(dist[i]);
    }
    return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    int N;
    const int INF = (1 << 28) - 1;
    int dist[2048];
    vector<tuple<int,int,int> > ev;
    bool upd[2048];
    bool relax(){
        bool chg = false;
        for(auto e : ev){
            int u,v,w;
            tie(u,v,w) = e;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                upd[v] = true;
                chg = true;
            }
        }
        return chg;
    }
    void updateval(){
        bool cont = false;
        for(int i = 0; i < N; i++){
            if(upd[i]){
                cont = true;
            }
        }
        if(!cont) return;
        vector<int> send;
        for(int i = 0; i < N; i++){
            if(upd[i]){
                send.push_back(dist[i]);
                SendB(true);
            }else{
                SendB(false);
            }
        }
        for(auto x : send){
            for(int j = 0; j < 28; j++){
                if(x & (1 << j)) SendB(true);
                else SendB(false);
            }
        }
    }
    vector<bool> cur;
    vector<int> dat;
    int popcount = 0;
}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    ::N = N;
    for(int i = 0; i < N; i++) dist[i] = INF;
    dist[0] = 0;
    for(int i = 0; i < B; i++){
        ev.emplace_back(S[i], T[i], D[i]);
        ev.emplace_back(T[i], S[i], D[i]);
    }
    while(relax()); // you are doing fine.
    updateval();
}

void ReceiveB(bool y) {
    if(cur.size() < N){
        if(y) popcount++;
        cur.push_back(y);
    }else if(cur.size() - N < 28*popcount-1){
        cur.push_back(y);
    }else if(cur.size() - N == 28*popcount-1){
        cur.push_back(y);
        for(int i = N; i < cur.size(); i += 28){
            int s = 0;
            for(int j = 0; j < 28; j++){
                s += cur[i+j] ? 1 << j : 0;
            }
            dat.push_back(s);
        }
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(cur[i]){
                dist[i] = min(dist[i], dat[cnt]);
                cnt++;
            }
        }
        memset(upd, false, sizeof(upd));
        while(relax());
        cur.clear();
        dat.clear();
        popcount = 0;
        updateval();
    }
}
/*
4 3 4
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7
 */

Compilation message

Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cur.size() < N){
        ~~~~~~~~~~~^~~
Azer.cpp:68:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     }else if(cur.size() - N < 28*popcount-1){
              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Azer.cpp:70:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     }else if(cur.size() - N == 28*popcount-1){
              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
Azer.cpp:72:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = N; i < cur.size(); i += 28){
                        ~~^~~~~~~~~~~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cur.size() < N){
        ~~~~~~~~~~~^~~
Baijan.cpp:70:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     }else if(cur.size() - N < 28*popcount-1){
              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
Baijan.cpp:72:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     }else if(cur.size() - N == 28*popcount-1){
              ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
Baijan.cpp:74:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = N; i < cur.size(); i += 28){
                        ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 1576 KB Output is correct
2 Correct 8 ms 1248 KB Output is correct
3 Correct 924 ms 1528 KB Output is correct
4 Correct 1162 ms 23776 KB Output is correct
5 Correct 62 ms 1832 KB Output is correct
6 Correct 896 ms 4248 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 992 KB Output is correct
2 Incorrect 427 ms 824 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 1648 KB Output is correct
2 Correct 393 ms 1344 KB Output is correct
3 Correct 1046 ms 21680 KB Output is correct
4 Correct 248 ms 1648 KB Output is correct
5 Incorrect 543 ms 10000 KB Wrong Answer [2]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 1648 KB Output is correct
2 Correct 393 ms 1344 KB Output is correct
3 Correct 1046 ms 21680 KB Output is correct
4 Correct 248 ms 1648 KB Output is correct
5 Incorrect 543 ms 10000 KB Wrong Answer [2]
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 1648 KB Output is correct
2 Correct 393 ms 1344 KB Output is correct
3 Correct 1046 ms 21680 KB Output is correct
4 Correct 248 ms 1648 KB Output is correct
5 Incorrect 543 ms 10000 KB Wrong Answer [2]
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 1576 KB Output is correct
2 Correct 8 ms 1248 KB Output is correct
3 Correct 924 ms 1528 KB Output is correct
4 Correct 1162 ms 23776 KB Output is correct
5 Correct 62 ms 1832 KB Output is correct
6 Correct 896 ms 4248 KB Output is correct
7 Correct 6 ms 992 KB Output is correct
8 Incorrect 427 ms 824 KB Wrong Answer [2]
9 Halted 0 ms 0 KB -