oj.uz

답안 #1105267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105267 2024-10-25T22:40:38 Z ThegeekKnight16 Spy 3 (JOI24_spy3) C++17
0 / 100
 1000 ms 4780 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;
            }
        }
    }
    cerr << "Arvore: "; for (auto x : MarcMuda) cerr << x << " "; cerr << '\n';

    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';
    string s;
    vector<bool> MarcRuim(M); for (auto x : X) MarcRuim[x] = 1;
    for (int i = 0; i < M; i++) if (MarcRuim[ids[i]])
    {
        for (ll k = 39; k >= 0; k--) s += '0' + ((C[ids[i]]>>k)&1LL);
    }
    return s;
    /*vector<int> MarcMuda(M);
    dijkstraAOI123(0, grafo, MarcRuim, MarcMuda);

    cerr << "MarcMuda(AOI): " << '\n';
    for (auto x : MarcMuda) cerr << x << " "; cerr << '\n';

    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)
            {
                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]);});

    vector<bool> MarcRuim(M); for (auto x : X) MarcRuim[x] = 1;
    int pos = 0;
    for (int i = 0; i < M; i++) if (MarcRuim[ids[i]])
    {
        ll p = 0;
        for (int k = 0; k < 40; k++) p = (p << 1LL) + (ll)(s[pos+k]-'0');
        C[ids[i]] = p; pos += 40;
    }

    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<int> MarcMuda(M);
    dijkstraBIT321(0, grafo, MarcRuim, MarcMuda);

    // cerr << "MarcMuda(BIT): " << '\n';
    // for (auto x : MarcMuda) cerr << x << " "; cerr << '\n';
    //
    // 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;
    // }
    // cerr << "Arvore achei: " << '\n';
    // for (auto x : MarcMuda) cerr << x << " "; cerr << '\n';

    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, -1), Marc(N);
    dfs(0, 0, -1, pai, paiE, grafo2, Marc);

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

Compilation message

Aoi.cpp:8:6: warning: 'void {anonymous}::dijkstraAOI123(int, const std::vector<std::vector<std::tuple<int, long long int, int, int> > >&, const std::vector<bool>&, std::vector<int>&)' defined but not used [-Wunused-function]
    8 | void dijkstraAOI123(int S, const vector<vector<tuple<int, ll, int, int>>> &grafo, const vector<bool> &MarcRuim, vector<int> &MarcMuda)
      |      ^~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1090 ms 4780 KB Time limit exceeded
2 Halted 0 ms 0 KB -