oj.uz

Submission #266579

# Submission time Handle Problem Language Result Execution time Memory
266579 2020-08-15T11:16:42 Z dolphingarlic Two Transportations (JOI19_transportations) C++14
70 / 100
 2080 ms 113008 KB 
#include "Azer.h"

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

namespace {
int N, stage = 0, cnt, mx_so_far;
vector<pair<int, int>> graph[2000];
vector<int> shortest;
priority_queue<pair<int, int>> pq;
bool visited[2000];
pair<int, int> candidate = {0, 0};

void reset() {
    visited[candidate.second] = true;
    shortest[candidate.second] = candidate.first;
    mx_so_far = candidate.first;
    for (pair<int, int> i : graph[candidate.second])
        pq.push({-candidate.first - i.second, i.first});
    N--;

    if (!N) return;

    while (pq.size() && visited[pq.top().second]) pq.pop();
    if (pq.size()) candidate = {-pq.top().first, pq.top().second};
    else candidate = {mx_so_far + 511, -1};

    for (int i = 0; i < 9; i++) SendA((candidate.first - mx_so_far & (1 << i)) >> i);
    cnt = stage = 0;
}
}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    ::N = N;
    shortest.resize(N);
    for (int i = 0; i < A; i++) {
        graph[U[i]].push_back({V[i], C[i]});
        graph[V[i]].push_back({U[i], C[i]});
    }
    reset();
}

void ReceiveA(bool x) {
    if (stage == 0) {
        if (x) {
            stage++;
            candidate = {0, 0};
        } else {
            for (int i = 0; i < 11; i++) SendA((candidate.second & (1 << i)) >> i);
            reset();
        }
    } else if (stage == 1) {
        candidate.first |= x << cnt++;
        if (cnt == 9) {
            candidate.first += mx_so_far;
            stage++;
            cnt = 0;
        }
    } else {
        candidate.second |= x << cnt++;
        if (cnt == 11) reset();
    }
}

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

#include "Baijan.h"

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

namespace {
int N, stage = 0, cnt, a_shortest, mx_so_far;
vector<pair<int, int>> graph[2000];
vector<int> shortest;
priority_queue<pair<int, int>> pq;
bool visited[2000];
pair<int, int> candidate = {0, 0};

void reset() {
    visited[candidate.second] = true;
    shortest[candidate.second] = candidate.first;
    mx_so_far = candidate.first;
    for (pair<int, int> i : graph[candidate.second])
        pq.push({-candidate.first - i.second, i.first});

    while (pq.size() && visited[pq.top().second]) pq.pop();
    if (pq.size()) candidate = {-pq.top().first, pq.top().second};
    else candidate = {mx_so_far + 511, -1};

    cnt = stage = a_shortest = 0;
}
}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
    ::N = N;
    shortest.resize(N);
    for (int i = 0; i < B; i++) {
        graph[S[i]].push_back({T[i], D[i]});
        graph[T[i]].push_back({S[i], D[i]});
    }
    reset();
}

void ReceiveB(bool y) {
    if (stage == 0) {
        a_shortest |= y << cnt++;
        if (cnt == 9) {
            if (a_shortest > candidate.first - mx_so_far) {
                SendB(1);
                for (int i = 0; i < 9; i++) SendB((candidate.first - mx_so_far & (1 << i)) >> i);
                for (int i = 0; i < 11; i++) SendB((candidate.second & (1 << i)) >> i);
                reset();
            } else {
                SendB(0);
                cnt = 0;
                candidate = {a_shortest + mx_so_far, 0};
                stage++;
            }
        }
    } else if (stage == 1) {
        candidate.second |= y << cnt++;
        if (cnt == 11) reset();
    }
}

Compilation message

Azer.cpp: In function 'void {anonymous}::reset()':
Azer.cpp:28:56: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |     for (int i = 0; i < 9; i++) SendA((candidate.first - mx_so_far & (1 << i)) >> i);
      |                                        ~~~~~~~~~~~~~~~~^~~~~~~~~~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:45:68: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   45 |                 for (int i = 0; i < 9; i++) SendB((candidate.first - mx_so_far & (1 << i)) >> i);
      |                                                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 758 ms 1920 KB Output is correct
3 Correct 926 ms 1792 KB Output is correct
4 Correct 1776 ms 55008 KB Output is correct
5 Correct 1202 ms 57328 KB Output is correct
6 Correct 224 ms 1536 KB Output is correct
7 Correct 1452 ms 58008 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 1648 KB Output is correct
2 Correct 2 ms 1360 KB Output is correct
3 Incorrect 635 ms 768 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 1760 KB Output is correct
2 Correct 400 ms 1520 KB Output is correct
3 Correct 650 ms 24488 KB Output is correct
4 Correct 292 ms 1760 KB Output is correct
5 Correct 830 ms 17408 KB Output is correct
6 Correct 328 ms 1536 KB Output is correct
7 Correct 456 ms 1560 KB Output is correct
8 Correct 408 ms 1536 KB Output is correct
9 Correct 722 ms 47088 KB Output is correct
10 Correct 1168 ms 47160 KB Output is correct
11 Correct 1658 ms 85432 KB Output is correct
12 Correct 1300 ms 79656 KB Output is correct
13 Correct 458 ms 1952 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 1760 KB Output is correct
2 Correct 400 ms 1520 KB Output is correct
3 Correct 650 ms 24488 KB Output is correct
4 Correct 292 ms 1760 KB Output is correct
5 Correct 830 ms 17408 KB Output is correct
6 Correct 328 ms 1536 KB Output is correct
7 Correct 456 ms 1560 KB Output is correct
8 Correct 408 ms 1536 KB Output is correct
9 Correct 722 ms 47088 KB Output is correct
10 Correct 1168 ms 47160 KB Output is correct
11 Correct 1658 ms 85432 KB Output is correct
12 Correct 1300 ms 79656 KB Output is correct
13 Correct 458 ms 1952 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct
15 Correct 568 ms 1592 KB Output is correct
16 Correct 364 ms 1536 KB Output is correct
17 Correct 364 ms 1536 KB Output is correct
18 Correct 736 ms 17600 KB Output is correct
19 Correct 512 ms 1576 KB Output is correct
20 Correct 894 ms 18168 KB Output is correct
21 Correct 557 ms 1536 KB Output is correct
22 Correct 702 ms 1536 KB Output is correct
23 Correct 973 ms 53048 KB Output is correct
24 Correct 1432 ms 53184 KB Output is correct
25 Correct 2041 ms 102816 KB Output is correct
26 Correct 1526 ms 89520 KB Output is correct
27 Correct 545 ms 2016 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 1760 KB Output is correct
2 Correct 400 ms 1520 KB Output is correct
3 Correct 650 ms 24488 KB Output is correct
4 Correct 292 ms 1760 KB Output is correct
5 Correct 830 ms 17408 KB Output is correct
6 Correct 328 ms 1536 KB Output is correct
7 Correct 456 ms 1560 KB Output is correct
8 Correct 408 ms 1536 KB Output is correct
9 Correct 722 ms 47088 KB Output is correct
10 Correct 1168 ms 47160 KB Output is correct
11 Correct 1658 ms 85432 KB Output is correct
12 Correct 1300 ms 79656 KB Output is correct
13 Correct 458 ms 1952 KB Output is correct
14 Correct 2 ms 1536 KB Output is correct
15 Correct 568 ms 1592 KB Output is correct
16 Correct 364 ms 1536 KB Output is correct
17 Correct 364 ms 1536 KB Output is correct
18 Correct 736 ms 17600 KB Output is correct
19 Correct 512 ms 1576 KB Output is correct
20 Correct 894 ms 18168 KB Output is correct
21 Correct 557 ms 1536 KB Output is correct
22 Correct 702 ms 1536 KB Output is correct
23 Correct 973 ms 53048 KB Output is correct
24 Correct 1432 ms 53184 KB Output is correct
25 Correct 2041 ms 102816 KB Output is correct
26 Correct 1526 ms 89520 KB Output is correct
27 Correct 545 ms 2016 KB Output is correct
28 Correct 1064 ms 1544 KB Output is correct
29 Correct 556 ms 1536 KB Output is correct
30 Correct 1468 ms 44008 KB Output is correct
31 Correct 890 ms 1536 KB Output is correct
32 Correct 1248 ms 37552 KB Output is correct
33 Correct 546 ms 1600 KB Output is correct
34 Correct 650 ms 1792 KB Output is correct
35 Correct 710 ms 1792 KB Output is correct
36 Correct 1146 ms 57952 KB Output is correct
37 Correct 1692 ms 58160 KB Output is correct
38 Correct 2080 ms 113008 KB Output is correct
39 Correct 1822 ms 102248 KB Output is correct
40 Correct 464 ms 2144 KB Output is correct

Subtask #7
0 / 16.0

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