oj.uz

Submission #1051077

# Submission time Handle Problem Language Result Execution time Memory
1051077 2024-08-09T19:18:56 Z beaconmc Spy 3 (JOI24_spy3) C++17
0 / 100
 1000 ms 10264 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];
            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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 8984 KB Partially correct
2 Correct 2 ms 2320 KB Output is correct
3 Partially correct 67 ms 8380 KB Partially correct
4 Partially correct 62 ms 8112 KB Partially correct
5 Partially correct 75 ms 8576 KB Partially correct
6 Partially correct 78 ms 8376 KB Partially correct
7 Partially correct 70 ms 8516 KB Partially correct
8 Partially correct 74 ms 8376 KB Partially correct
9 Partially correct 55 ms 7956 KB Partially correct
10 Correct 25 ms 8304 KB Output is correct
11 Partially correct 71 ms 8460 KB Partially correct
12 Correct 79 ms 8420 KB Output is correct
13 Partially correct 68 ms 8224 KB Partially correct
14 Partially correct 58 ms 8380 KB Partially correct
15 Correct 62 ms 8108 KB Output is correct
16 Correct 19 ms 7860 KB Output is correct
17 Partially correct 100 ms 8508 KB Partially correct
18 Partially correct 98 ms 8244 KB Partially correct
19 Partially correct 131 ms 10244 KB Partially correct
20 Partially correct 104 ms 10216 KB Partially correct
21 Partially correct 127 ms 10264 KB Partially correct
22 Execution timed out 1130 ms 10224 KB Time limit exceeded
23 Halted 0 ms 0 KB -