oj.uz

Submission #708212

# Submission time Handle Problem Language Result Execution time Memory
708212 2023-03-11T10:08:58 Z LittleCube Two Transportations (JOI19_transportations) C++14
14 / 100
 445 ms 27988 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() / 32; i++)
        {
            long long cur = 0;
            for (int p = 0; p < 32; p++)
                cur = cur * 2 + receive[i * 32 + 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++)
        {
            long long cur = S[i] * 2000 * 500 + T[i] * 500 + D[i] - 1;
            for (int p = 31; 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() / 32; 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 313 ms 1176 KB Output is correct
2 Correct 2 ms 656 KB Output is correct
3 Correct 356 ms 1160 KB Output is correct
4 Correct 385 ms 10844 KB Output is correct
5 Correct 20 ms 936 KB Output is correct
6 Correct 303 ms 2848 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 656 KB Output is correct
2 Correct 243 ms 904 KB Output is correct
3 Correct 275 ms 1012 KB Output is correct
4 Correct 317 ms 27988 KB Output is correct
5 Correct 154 ms 24288 KB Output is correct
6 Correct 67 ms 704 KB Output is correct
7 Correct 445 ms 24940 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 928 KB Output is correct
2 Correct 1 ms 528 KB Output is correct
3 Correct 316 ms 1328 KB Output is correct
4 Correct 281 ms 956 KB Output is correct
5 Correct 240 ms 1100 KB Output is correct
6 Correct 263 ms 900 KB Output is correct
7 Correct 97 ms 816 KB Output is correct
8 Runtime error 0 ms 340 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 103 ms 800 KB Output is correct
2 Correct 190 ms 1112 KB Output is correct
3 Runtime error 24 ms 4408 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 103 ms 800 KB Output is correct
2 Correct 190 ms 1112 KB Output is correct
3 Runtime error 24 ms 4408 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 103 ms 800 KB Output is correct
2 Correct 190 ms 1112 KB Output is correct
3 Runtime error 24 ms 4408 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 313 ms 1176 KB Output is correct
2 Correct 2 ms 656 KB Output is correct
3 Correct 356 ms 1160 KB Output is correct
4 Correct 385 ms 10844 KB Output is correct
5 Correct 20 ms 936 KB Output is correct
6 Correct 303 ms 2848 KB Output is correct
7 Correct 1 ms 656 KB Output is correct
8 Correct 243 ms 904 KB Output is correct
9 Correct 275 ms 1012 KB Output is correct
10 Correct 317 ms 27988 KB Output is correct
11 Correct 154 ms 24288 KB Output is correct
12 Correct 67 ms 704 KB Output is correct
13 Correct 445 ms 24940 KB Output is correct
14 Correct 244 ms 928 KB Output is correct
15 Correct 1 ms 528 KB Output is correct
16 Correct 316 ms 1328 KB Output is correct
17 Correct 281 ms 956 KB Output is correct
18 Correct 240 ms 1100 KB Output is correct
19 Correct 263 ms 900 KB Output is correct
20 Correct 97 ms 816 KB Output is correct
21 Runtime error 0 ms 340 KB Execution killed with signal 13
22 Halted 0 ms 0 KB -