oj.uz

Submission #1105265

# Submission time Handle Problem Language Result Execution time Memory
1105265 2024-10-25T22:23:18 Z ThegeekKnight16 Spy 3 (JOI24_spy3) C++17
0 / 100
 1000 ms 2384 KB 
#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

namespace{
void dijkstraAOI123(int S, const vector<vector<tuple<int, ll, int, int>>> &grafo, const vector<bool> &MarcRuim, vector<int> &MarcMuda)
{
    int N = grafo.size();

    vector<ll> Dist(N, INF), pai(N);
    set<pair<ll, int>> fora;
    fora.emplace(Dist[S] = 0LL, S);

    while (!fora.empty())
    {
        auto [d, v] = *fora.begin(); fora.erase(fora.begin());
        if (v != 0) MarcMuda[pai[v]] ^= 1;

        for (auto [viz, p, i, id] : grafo[v])
        {
            if (Dist[viz] > d + p)
            {
                fora.erase(make_pair(Dist[viz], viz));
                fora.emplace(Dist[viz] = d + p, viz); pai[viz] = i;
            }
        }
    }

    fora.clear(); fill(Dist.begin(), Dist.end(), INF);
    fora.emplace(Dist[S] = 0LL, S);

    while (!fora.empty())
    {
        auto [d, v] = *fora.begin(); fora.erase(fora.begin());
        if (v != 0) MarcMuda[pai[v]] ^= 1;

        for (auto [viz, p, i, id] : grafo[v])
        {
            if (Dist[viz] > d + p && !MarcRuim[id])
            {
                fora.erase(make_pair(Dist[viz], viz));
                fora.emplace(Dist[viz] = d + p, viz); pai[viz] = i;
            }
        }
    }
}
}

string aoi(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<ll> C, vector<int> T, vector<int> X)
{
    vector<vector<tuple<int, ll, int, int>>> grafo(N);
    vector<int> ids(M); iota(ids.begin(), ids.end(), 0); sort(ids.begin(), ids.end(), [&](const int &a, const int &b) {return make_pair(A[a], B[a]) < make_pair(A[b], B[b]);});
    for (int i = 0; i < M; i++)
    {
        int id = ids[i];
        int X = A[id], Y = B[id], P = C[id];
        grafo[X].emplace_back(Y, P, i, id);
        grafo[Y].emplace_back(X, P, i, id);
    }
    for (auto &x : grafo) sort(x.begin(), x.end());

    // cerr << "PENIS" << '\n';
    vector<bool> MarcRuim(M); for (auto x : X) MarcRuim[x] = 1;
    vector<int> MarcMuda(M);
    dijkstraAOI123(0, grafo, MarcRuim, MarcMuda);

    string s;
    for (int i = 0; i < M; i++) if (MarcMuda[i])
        for (int k = 14; k >= 0; k--) s += '0' + ((i>>k)&1);
    return s;
}

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

typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

namespace{
void dijkstraBIT321(int S, const vector<vector<tuple<int, ll, int, int>>> &grafo, const vector<bool> &MarcRuim, vector<int> &MarcMuda)
{
    int N = grafo.size();

    vector<ll> Dist(N, INF), pai(N);
    set<pair<ll, int>> fora;
    fora.emplace(Dist[S] = 0LL, S);

    while (!fora.empty())
    {
        auto [d, v] = *fora.begin(); fora.erase(fora.begin());
        if (v != 0) MarcMuda[pai[v]] ^= 1;

        for (auto [viz, p, i, id] : grafo[v])
        {
            if (Dist[viz] > d + p && !MarcRuim[id])
            {
                fora.erase(make_pair(Dist[viz], viz));
                fora.emplace(Dist[viz] = d + p, viz); pai[viz] = i;
            }
        }
    }
}

void dfs(int v, int p, int e, vector<int> &pai, vector<int> &paiE, const vector<vector<pair<int, int>>> &grafo, vector<int> &Marc)
{
    pai[v] = p; paiE[v] = e;
    Marc[v] = 1;

    for (auto [viz, id] : grafo[v])
    {
        if (Marc[viz]) continue;
        dfs(viz, v, id, pai, paiE, grafo, Marc);
    }
}
}

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)
{
    vector<vector<tuple<int, ll, int, int>>> grafo(N);
    vector<int> ids(M); iota(ids.begin(), ids.end(), 0); sort(ids.begin(), ids.end(), [&](const int &a, const int &b) {return make_pair(A[a], B[a]) < make_pair(A[b], B[b]);});
    for (int i = 0; i < M; i++)
    {
        int id = ids[i];
        int X = A[id], Y = B[id], P = C[id];
        grafo[X].emplace_back(Y, P, i, id);
        grafo[Y].emplace_back(X, P, i, id);
    }
    for (auto &x : grafo) sort(x.begin(), x.end());

    // cerr << "PENIS" << '\n';
    vector<bool> MarcRuim(M); for (auto x : X) MarcRuim[x] = 1;
    vector<int> MarcMuda(M);
    dijkstraBIT321(0, grafo, MarcRuim, MarcMuda);

    for (int i = 0; i < s.size(); i += 15)
    {
        int id = 0;
        for (int k = 0; k < 15; k++) id = (id << 1) + (int)(s[i+k]-'0');
        MarcMuda[id] ^= 1;
    }

    vector<vector<pair<int, int>>> grafo2(N);
    for (int i = 0; i < M; i++) if (MarcMuda[i])
    {
        int X = A[ids[i]], Y = B[ids[i]];
        grafo2[X].emplace_back(Y, ids[i]); grafo2[Y].emplace_back(X, ids[i]);
    }

    vector<int> pai(N), paiE(N), Marc(N);
    dfs(0, 0, 0, pai, paiE, grafo2, Marc);

    for (int q = 0; q < Q; q++)
    {
        int X = T[q];
        vector<int> path;
        while (X != pai[X]) path.push_back(paiE[X]), X = pai[X];
        reverse(path.begin(), path.end());
        answer(path);
    }
}

Compilation message

Bitaro.cpp: In function 'void bitaro(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::string)':
Bitaro.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < s.size(); i += 15)
      |                     ~~^~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 2384 KB Time limit exceeded
2 Halted 0 ms 0 KB -