oj.uz

Submission #1051078

# Submission time Handle Problem Language Result Execution time Memory
1051078 2024-08-09T19:19:55 Z beaconmc Spy 3 (JOI24_spy3) C++17
23 / 100
 187 ms 13144 KB 
#include "Aoi.h"
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

namespace {

const ll INF = 10000000000000000;
const ll maxn = 10005;
vector<basic_string<ll>> edges[maxn];
basic_string<ll> prevs[maxn];
ll dists[maxn];
bool visited[maxn];


}  // namespace


string aoi(int N, int M, int Q, int K, vector<int> A,vector<int> B, vector<long long> C,
                vector<int> T, vector<int> X) {
    string ans;

    FOR(i,0,M){
        edges[A[i]].push_back({B[i], C[i], i});
        edges[B[i]].push_back({A[i], C[i], i});
    }
    FOR(i,0,Q){
        FOR(k,0,maxn) dists[k] = INF, prevs[k] = {-1, -1}, visited[k] = 0;


        priority_queue<basic_string<ll>> pq;

        dists[0] = 0;

        pq.push({0, 0});
        while (pq.size()){
            basic_string<ll> node = pq.top();
 
            if (node[1] == T[i]) break;

            pq.pop();
            node[0] = -node[0];
            if (node[0] != dists[node[1]]) continue;
            for (auto&i : edges[node[1]]){
                if (dists[i[0]] > node[0] + i[1]){
                    prevs[i[0]] = {node[1], i[2]};
                    dists[i[0]] = node[0] + i[1];
                    pq.push({-dists[i[0]], i[0]});
                }
            }
        }
        unordered_set<ll> stuff;
        ll cur = T[i];

        
        while (prevs[cur][1] != -1){
            stuff.insert(prevs[cur][1]);
            cur = prevs[cur][0];
        }


        FOR(j,0,K){
            if (stuff.count(X[j])) ans += '1';
            else ans += '0';
        }

    }
    return ans;


}

#include "Bitaro.h"
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;
namespace {
const ll INF = 10000000000000000;
const ll maxn = 10005;
vector<basic_string<ll>> edges[maxn];
basic_string<ll> prevs[maxn];
ll dists[maxn];
bool visited[maxn];
}  // namespace




void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B,
            vector<long long> C, vector<int> T, vector<int> X,
            string s) {



    FOR(i,0,M){
        edges[A[i]].push_back({B[i], C[i], i});
        edges[B[i]].push_back({A[i], C[i], i});
    }
    FOR(i,0,Q){

        FOR(k,0,maxn) dists[k] = INF, prevs[k] = {-1, -1}, visited[k] = 0;
        unordered_set<ll> idk;
        FOR(j, K*i, K*(i+1)){
            if (s[j] == '1') idk.insert(X[j-K*i]);
        }

        unordered_set<ll> idkman;
        for (auto&i : X) idkman.insert(i);

        FOR(i,0,maxn){
            for (auto&j : edges[i]){
                if (idk.count(j[2])) j[1] = 1;
                else if (idkman.count(j[2])) j[1] = INF;
            }
           

        }


        priority_queue<basic_string<ll>> pq;

        dists[0] = 0;

        pq.push({0, 0});
        while (pq.size()){
            basic_string<ll> node = pq.top();
            if (node[1] == T[i]) break;
            pq.pop();
            node[0] = -node[0];
             if (node[0] != dists[node[1]]) continue;
            for (auto&i : edges[node[1]]){
                if (dists[i[0]] > node[0] + i[1]){
                    prevs[i[0]] = {node[1], i[2]};
                    dists[i[0]] = node[0] + i[1];
                    pq.push({-dists[i[0]], i[0]});
                }
            }
        }

        vector<int> stuff;

        ll cur = T[i];
        
        while (prevs[cur][1] != -1){
            stuff.push_back(prevs[cur][1]);
            cur = prevs[cur][0];
        }

        reverse(stuff.begin(), stuff.end());

        answer(stuff);



    }


}

Subtask #1
23.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 28 ms 10936 KB Partially correct
2 Correct 2 ms 2832 KB Output is correct
3 Partially correct 72 ms 10488 KB Partially correct
4 Partially correct 70 ms 9804 KB Partially correct
5 Partially correct 84 ms 10680 KB Partially correct
6 Partially correct 87 ms 10676 KB Partially correct
7 Partially correct 74 ms 10424 KB Partially correct
8 Partially correct 78 ms 10428 KB Partially correct
9 Partially correct 63 ms 9664 KB Partially correct
10 Correct 25 ms 9908 KB Output is correct
11 Partially correct 75 ms 10496 KB Partially correct
12 Correct 86 ms 10832 KB Output is correct
13 Partially correct 73 ms 10436 KB Partially correct
14 Partially correct 67 ms 10540 KB Partially correct
15 Correct 68 ms 9956 KB Output is correct
16 Correct 17 ms 9964 KB Output is correct
17 Partially correct 112 ms 10056 KB Partially correct
18 Partially correct 98 ms 10364 KB Partially correct
19 Partially correct 137 ms 12724 KB Partially correct
20 Partially correct 112 ms 12828 KB Partially correct
21 Partially correct 138 ms 12836 KB Partially correct
22 Partially correct 179 ms 12564 KB Partially correct
23 Partially correct 117 ms 12868 KB Partially correct
24 Partially correct 187 ms 12584 KB Partially correct
25 Partially correct 116 ms 10320 KB Partially correct
26 Partially correct 108 ms 10324 KB Partially correct
27 Correct 4 ms 2828 KB Output is correct
28 Partially correct 59 ms 11400 KB Partially correct
29 Partially correct 44 ms 7868 KB Partially correct
30 Correct 59 ms 11468 KB Output is correct
31 Correct 39 ms 11016 KB Output is correct
32 Partially correct 69 ms 10936 KB Partially correct
33 Correct 74 ms 10656 KB Output is correct
34 Partially correct 65 ms 11444 KB Partially correct
35 Correct 54 ms 11696 KB Output is correct
36 Partially correct 62 ms 11432 KB Partially correct
37 Partially correct 20 ms 6396 KB Partially correct
38 Partially correct 45 ms 7620 KB Partially correct
39 Partially correct 46 ms 7348 KB Partially correct
40 Correct 11 ms 6960 KB Output is correct
41 Partially correct 54 ms 12028 KB Partially correct
42 Partially correct 43 ms 12280 KB Partially correct
43 Correct 86 ms 12604 KB Output is correct
44 Correct 19 ms 12068 KB Output is correct
45 Partially correct 30 ms 6272 KB Partially correct
46 Partially correct 39 ms 7016 KB Partially correct
47 Correct 37 ms 7152 KB Output is correct
48 Correct 2 ms 2828 KB Output is correct
49 Correct 2 ms 2828 KB Output is correct
50 Partially correct 24 ms 11032 KB Partially correct
51 Partially correct 6 ms 3344 KB Partially correct
52 Partially correct 5 ms 2836 KB Partially correct
53 Partially correct 34 ms 11020 KB Partially correct
54 Partially correct 22 ms 8468 KB Partially correct
55 Partially correct 47 ms 9188 KB Partially correct
56 Partially correct 43 ms 11796 KB Partially correct
57 Partially correct 75 ms 12292 KB Partially correct
58 Partially correct 63 ms 9644 KB Partially correct
59 Partially correct 105 ms 12400 KB Partially correct
60 Partially correct 78 ms 12092 KB Partially correct
61 Partially correct 86 ms 12304 KB Partially correct
62 Partially correct 81 ms 11456 KB Partially correct
63 Partially correct 99 ms 12356 KB Partially correct
64 Correct 20 ms 10504 KB Output is correct
65 Partially correct 64 ms 9016 KB Partially correct
66 Partially correct 41 ms 13144 KB Partially correct
67 Partially correct 69 ms 9028 KB Partially correct
68 Partially correct 51 ms 13124 KB Partially correct
69 Correct 2 ms 2840 KB Output is correct
70 Correct 2 ms 2836 KB Output is correct
71 Correct 3 ms 2828 KB Output is correct
72 Partially correct 22 ms 6416 KB Partially correct
73 Partially correct 48 ms 7436 KB Partially correct
74 Partially correct 58 ms 7100 KB Partially correct
75 Correct 13 ms 6928 KB Output is correct
76 Correct 2 ms 2840 KB Output is correct
77 Correct 57 ms 11012 KB Output is correct
78 Partially correct 53 ms 11048 KB Partially correct
79 Correct 63 ms 10932 KB Output is correct
80 Correct 2 ms 2840 KB Output is correct
81 Partially correct 68 ms 10420 KB Partially correct
82 Partially correct 61 ms 10556 KB Partially correct
83 Partially correct 71 ms 10360 KB Partially correct