oj.uz

Submission #708208

# Submission time Handle Problem Language Result Execution time Memory
708208 2023-03-11T10:01:31 Z LittleCube Two Transportations (JOI19_transportations) C++14
14 / 100
 440 ms 27920 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
    int N;
    bool state;
    vector<int> receive, U, V, C;
} // namespace
vector<int> E[2005];

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C)
{
    ::N = N;
    ::U = U;
    ::V = V;
    ::C = C;
    SendA(state = U.empty());
}

void ReceiveA(bool x)
{
    receive.emplace_back(x);
}

std::vector<int> Answer()
{
    vector<int> ans(N);
    if (state)
    {
        for (int i = 0; i < N; i++)
            for (int p = 0; p < 20; p++)
                ans[i] = ans[i] * 2 + receive[i * 20 + p];
    }
    else
    {
        for (int i = 0; i < receive.size() / 31; i++)
        {
            unsigned cur = 0;
            for (int p = 0; p < 31; p++)
                cur = cur * 2 + receive[i * 31 + p];
            cerr << i << ' ' << (cur / 500 / 2000) << ' ' << (cur / 500 % 2000) << ' ' << (cur % 500 + 1) << '\n';
            U.emplace_back(cur / 500 / 2000);
            V.emplace_back(cur / 500 % 2000);
            C.emplace_back(cur % 500 + 1);
        }

        vector<int> dis(N, 1'000'000'000);
        vector<pii> E[2000];
        dis[0] = 0;
        for (int i = 0; i < U.size(); i++)
        {
            E[U[i]].emplace_back(pii(V[i], C[i]));
            E[V[i]].emplace_back(pii(U[i], C[i]));
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push(pii(0, 0));
        while (!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dis[u])
                continue;
            for (auto [v, w] : E[u])
                if (d + w < dis[v])
                {
                    dis[v] = d + w;
                    pq.push(pii(dis[v], v));
                }
        }
        ans = dis;
    }
    return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
    int N;
    vector<int> receive, S, T, D;
}

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D)
{
    ::N = N;
    ::S = S;
    ::T = T;
    ::D = D;
}

void ReceiveB(bool y)
{
    if (y)
    {
        vector<int> dis(N, 1'000'000'000);
        vector<pii> E[2000];
        dis[0] = 0;
        for (int i = 0; i < S.size(); i++)
        {
            E[S[i]].emplace_back(pii(T[i], D[i]));
            E[T[i]].emplace_back(pii(S[i], D[i]));
        }
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push(pii(0, 0));
        while (!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dis[u])
                continue;
            for (auto [v, w] : E[u])
                if (d + w < dis[v])
                {
                    dis[v] = d + w;
                    pq.push(pii(dis[v], v));
                }
        }
        for (int i = 0; i < N; i++)
            for (int p = 19; p >= 0; p--)
                SendB((dis[i] >> p) & 1);
    }
    else
    {
        for (int i = 0; i < S.size(); i++)
        {
            unsigned cur = S[i] * 2000 * 500 + T[i] * 500 + D[i] - 1;
            for (int p = 30; p >= 0; p--)
                SendB((cur >> p) & 1);
        }
    }
}

Compilation message

Azer.cpp: In function 'std::vector<int> Answer()':
Azer.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < receive.size() / 31; i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
Azer.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < U.size(); i++)
      |                         ~~^~~~~~~~~~
Azer.cpp:64:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |             auto [d, u] = pq.top();
      |                  ^
Azer.cpp:68:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |             for (auto [v, w] : E[u])
      |                       ^

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0; i < S.size(); i++)
      |                         ~~^~~~~~~~~~
Baijan.cpp:38:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |             auto [d, u] = pq.top();
      |                  ^
Baijan.cpp:42:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |             for (auto [v, w] : E[u])
      |                       ^
Baijan.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < S.size(); i++)
      |                         ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 1148 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 350 ms 1104 KB Output is correct
4 Correct 284 ms 10540 KB Output is correct
5 Correct 15 ms 928 KB Output is correct
6 Correct 365 ms 2664 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 265 ms 1004 KB Output is correct
3 Correct 246 ms 1016 KB Output is correct
4 Correct 326 ms 27920 KB Output is correct
5 Correct 132 ms 24236 KB Output is correct
6 Correct 65 ms 716 KB Output is correct
7 Correct 440 ms 25000 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 1128 KB Output is correct
2 Correct 1 ms 660 KB Output is correct
3 Correct 292 ms 1152 KB Output is correct
4 Correct 284 ms 984 KB Output is correct
5 Correct 278 ms 932 KB Output is correct
6 Correct 294 ms 960 KB Output is correct
7 Correct 140 ms 844 KB Output is correct
8 Runtime error 1 ms 328 KB Execution killed with signal 13
9 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 824 KB Output is correct
2 Correct 196 ms 1032 KB Output is correct
3 Runtime error 25 ms 4420 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 824 KB Output is correct
2 Correct 196 ms 1032 KB Output is correct
3 Runtime error 25 ms 4420 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 824 KB Output is correct
2 Correct 196 ms 1032 KB Output is correct
3 Runtime error 25 ms 4420 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 1148 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 350 ms 1104 KB Output is correct
4 Correct 284 ms 10540 KB Output is correct
5 Correct 15 ms 928 KB Output is correct
6 Correct 365 ms 2664 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 265 ms 1004 KB Output is correct
9 Correct 246 ms 1016 KB Output is correct
10 Correct 326 ms 27920 KB Output is correct
11 Correct 132 ms 24236 KB Output is correct
12 Correct 65 ms 716 KB Output is correct
13 Correct 440 ms 25000 KB Output is correct
14 Correct 233 ms 1128 KB Output is correct
15 Correct 1 ms 660 KB Output is correct
16 Correct 292 ms 1152 KB Output is correct
17 Correct 284 ms 984 KB Output is correct
18 Correct 278 ms 932 KB Output is correct
19 Correct 294 ms 960 KB Output is correct
20 Correct 140 ms 844 KB Output is correct
21 Runtime error 1 ms 328 KB Execution killed with signal 13
22 Halted 0 ms 0 KB -