oj.uz

Submission #266559

# Submission time Handle Problem Language Result Execution time Memory
266559 2020-08-15T11:01:20 Z dolphingarlic Two Transportations (JOI19_transportations) C++14
52 / 100
 2134 ms 102680 KB 
#include "Azer.h"

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

namespace {
int N, stage = 0, cnt;
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;
    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 = {INT_MAX, -1};

    for (int i = 0; i < 20; i++) SendA((candidate.first & (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 == 20) {
            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;
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;
    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 = {INT_MAX, -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 == 20) {
            if (a_shortest > candidate.first) {
                SendB(1);
                for (int i = 0; i < 20; i++) SendB((candidate.first & (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, 0};
                stage++;
            }
        }
    } else if (stage == 1) {
        candidate.second |= y << cnt++;
        if (cnt == 11) reset();
    }
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Incorrect 495 ms 768 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1536 KB Output is correct
2 Correct 756 ms 1536 KB Output is correct
3 Correct 726 ms 24344 KB Output is correct
4 Correct 684 ms 1760 KB Output is correct
5 Correct 812 ms 17448 KB Output is correct
6 Correct 664 ms 1536 KB Output is correct
7 Correct 676 ms 1536 KB Output is correct
8 Correct 736 ms 1536 KB Output is correct
9 Correct 848 ms 47088 KB Output is correct
10 Correct 1516 ms 47136 KB Output is correct
11 Correct 1794 ms 85088 KB Output is correct
12 Correct 1540 ms 79664 KB Output is correct
13 Correct 1062 ms 1960 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1536 KB Output is correct
2 Correct 756 ms 1536 KB Output is correct
3 Correct 726 ms 24344 KB Output is correct
4 Correct 684 ms 1760 KB Output is correct
5 Correct 812 ms 17448 KB Output is correct
6 Correct 664 ms 1536 KB Output is correct
7 Correct 676 ms 1536 KB Output is correct
8 Correct 736 ms 1536 KB Output is correct
9 Correct 848 ms 47088 KB Output is correct
10 Correct 1516 ms 47136 KB Output is correct
11 Correct 1794 ms 85088 KB Output is correct
12 Correct 1540 ms 79664 KB Output is correct
13 Correct 1062 ms 1960 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 846 ms 1448 KB Output is correct
16 Correct 774 ms 1536 KB Output is correct
17 Correct 604 ms 1536 KB Output is correct
18 Correct 966 ms 17792 KB Output is correct
19 Correct 718 ms 1536 KB Output is correct
20 Correct 1280 ms 18248 KB Output is correct
21 Correct 618 ms 1672 KB Output is correct
22 Correct 854 ms 1536 KB Output is correct
23 Correct 1077 ms 52640 KB Output is correct
24 Correct 1826 ms 52992 KB Output is correct
25 Correct 2134 ms 102680 KB Output is correct
26 Correct 1808 ms 89528 KB Output is correct
27 Correct 656 ms 2272 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 680 ms 1536 KB Output is correct
2 Correct 756 ms 1536 KB Output is correct
3 Correct 726 ms 24344 KB Output is correct
4 Correct 684 ms 1760 KB Output is correct
5 Correct 812 ms 17448 KB Output is correct
6 Correct 664 ms 1536 KB Output is correct
7 Correct 676 ms 1536 KB Output is correct
8 Correct 736 ms 1536 KB Output is correct
9 Correct 848 ms 47088 KB Output is correct
10 Correct 1516 ms 47136 KB Output is correct
11 Correct 1794 ms 85088 KB Output is correct
12 Correct 1540 ms 79664 KB Output is correct
13 Correct 1062 ms 1960 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 846 ms 1448 KB Output is correct
16 Correct 774 ms 1536 KB Output is correct
17 Correct 604 ms 1536 KB Output is correct
18 Correct 966 ms 17792 KB Output is correct
19 Correct 718 ms 1536 KB Output is correct
20 Correct 1280 ms 18248 KB Output is correct
21 Correct 618 ms 1672 KB Output is correct
22 Correct 854 ms 1536 KB Output is correct
23 Correct 1077 ms 52640 KB Output is correct
24 Correct 1826 ms 52992 KB Output is correct
25 Correct 2134 ms 102680 KB Output is correct
26 Correct 1808 ms 89528 KB Output is correct
27 Correct 656 ms 2272 KB Output is correct
28 Incorrect 485 ms 640 KB Wrong Answer [2]
29 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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