oj.uz

Submission #1051083

# Submission time Handle Problem Language Result Execution time Memory
1051083 2024-08-09T19:22:56 Z beaconmc Spy 3 (JOI24_spy3) C++17
23 / 100
 188 ms 10568 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<vector<ll>> edges[maxn];
vector<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<vector<ll>> pq;

        dists[0] = 0;

        pq.push({0, 0});
        while (pq.size()){
            vector<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<vector<ll>> edges[maxn];
vector<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<vector<ll>> pq;

        dists[0] = 0;

        pq.push({0, 0});
        while (pq.size()){
            vector<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 32 ms 8888 KB Partially correct
2 Correct 2 ms 2324 KB Output is correct
3 Partially correct 65 ms 8532 KB Partially correct
4 Partially correct 62 ms 8000 KB Partially correct
5 Partially correct 73 ms 8432 KB Partially correct
6 Partially correct 75 ms 8412 KB Partially correct
7 Partially correct 70 ms 8616 KB Partially correct
8 Partially correct 69 ms 8376 KB Partially correct
9 Partially correct 56 ms 7924 KB Partially correct
10 Correct 24 ms 8108 KB Output is correct
11 Partially correct 71 ms 8384 KB Partially correct
12 Correct 87 ms 8452 KB Output is correct
13 Partially correct 73 ms 8600 KB Partially correct
14 Partially correct 58 ms 8476 KB Partially correct
15 Correct 63 ms 8108 KB Output is correct
16 Correct 19 ms 7940 KB Output is correct
17 Partially correct 90 ms 8520 KB Partially correct
18 Partially correct 88 ms 8480 KB Partially correct
19 Partially correct 129 ms 10232 KB Partially correct
20 Partially correct 92 ms 10192 KB Partially correct
21 Partially correct 125 ms 10240 KB Partially correct
22 Partially correct 188 ms 10240 KB Partially correct
23 Partially correct 108 ms 10232 KB Partially correct
24 Partially correct 172 ms 10212 KB Partially correct
25 Partially correct 100 ms 8340 KB Partially correct
26 Partially correct 102 ms 8476 KB Partially correct
27 Correct 4 ms 2316 KB Output is correct
28 Partially correct 61 ms 8884 KB Partially correct
29 Partially correct 40 ms 6424 KB Partially correct
30 Correct 57 ms 9136 KB Output is correct
31 Correct 35 ms 8948 KB Output is correct
32 Partially correct 67 ms 9160 KB Partially correct
33 Correct 78 ms 8668 KB Output is correct
34 Partially correct 70 ms 9096 KB Partially correct
35 Correct 52 ms 9108 KB Output is correct
36 Partially correct 56 ms 9116 KB Partially correct
37 Partially correct 19 ms 5364 KB Partially correct
38 Partially correct 44 ms 6508 KB Partially correct
39 Partially correct 43 ms 6504 KB Partially correct
40 Correct 11 ms 5908 KB Output is correct
41 Partially correct 52 ms 9692 KB Partially correct
42 Partially correct 46 ms 9848 KB Partially correct
43 Correct 87 ms 10132 KB Output is correct
44 Correct 20 ms 9516 KB Output is correct
45 Partially correct 23 ms 5368 KB Partially correct
46 Partially correct 33 ms 6108 KB Partially correct
47 Correct 33 ms 5924 KB Output is correct
48 Correct 2 ms 2324 KB Output is correct
49 Correct 2 ms 2316 KB Output is correct
50 Partially correct 20 ms 8984 KB Partially correct
51 Partially correct 5 ms 2832 KB Partially correct
52 Partially correct 4 ms 2320 KB Partially correct
53 Partially correct 33 ms 8940 KB Partially correct
54 Partially correct 20 ms 6924 KB Partially correct
55 Partially correct 44 ms 7568 KB Partially correct
56 Partially correct 39 ms 9480 KB Partially correct
57 Partially correct 66 ms 9984 KB Partially correct
58 Partially correct 60 ms 7852 KB Partially correct
59 Partially correct 101 ms 9908 KB Partially correct
60 Partially correct 73 ms 9644 KB Partially correct
61 Partially correct 70 ms 9912 KB Partially correct
62 Partially correct 74 ms 9256 KB Partially correct
63 Partially correct 90 ms 9940 KB Partially correct
64 Correct 20 ms 8456 KB Output is correct
65 Partially correct 65 ms 7312 KB Partially correct
66 Partially correct 40 ms 10476 KB Partially correct
67 Partially correct 65 ms 7412 KB Partially correct
68 Partially correct 47 ms 10568 KB Partially correct
69 Correct 2 ms 2324 KB Output is correct
70 Correct 2 ms 2324 KB Output is correct
71 Correct 3 ms 2316 KB Output is correct
72 Partially correct 23 ms 5388 KB Partially correct
73 Partially correct 43 ms 5860 KB Partially correct
74 Partially correct 52 ms 5984 KB Partially correct
75 Correct 12 ms 5896 KB Output is correct
76 Correct 2 ms 2320 KB Output is correct
77 Correct 50 ms 8964 KB Output is correct
78 Partially correct 46 ms 9064 KB Partially correct
79 Correct 58 ms 9056 KB Output is correct
80 Correct 2 ms 2328 KB Output is correct
81 Partially correct 68 ms 8308 KB Partially correct
82 Partially correct 65 ms 8380 KB Partially correct
83 Partially correct 74 ms 8376 KB Partially correct