#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)
| ^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
4780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
