#include "Aoi.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
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)
{
const ll inf = 1e18 + 5;
vector<ll> d(n, inf);
vector<int>p(n, -1);
vector<vector<pair<int, ll> > > g(n);
for (int i = 0; i < m; i++) g[a[i]].push_back({ b[i], c[i] }), g[b[i]].push_back({ a[i], c[i] });
set<pair<ll, pair<int, int> > > pq;
pq.insert({ 0, {0, -1} });
while (!pq.empty())
{
ll di = pq.begin()->first;
int u = pq.begin()->second.first;
int pi = pq.begin()->second.second;
pq.erase(pq.begin());
if (d[u] != inf) continue;
d[u] = di;
p[u] = pi;
for (pair<int, ll> v : g[u]) if (d[v.first] == inf)
{
pq.insert({ d[u] + v.second, { v.first, u } });
}
}
map<pair<int, int>, int> id;
vector<pair<int, int> > anc;
string s;
for (int i = 0; i < k; i++)
{
if (d[a[x[i]]] < d[b[x[i]]]) s.push_back('0'), anc.push_back({ a[x[i]], b[x[i]] }), id[{ a[x[i]], b[x[i]] }] = i;
else s.push_back('1'), anc.push_back({ b[x[i]], a[x[i]] }), id[{ b[x[i]], a[x[i]] }] = i;
}
for (int i = 0; i < q; i++) anc.push_back({ t[i], t[i] });
for (int i = 0; i < anc.size(); i++)
{
int st = anc[i].first;
int x = 0;
while (st != 0)
{
if (id.count({ p[st], st }))
{
x = id[{ p[st], st }] + 1;
break;
}
st = p[st];
}
for (int b = 0; b < 9; b++) s.push_back((x & (1 << b)) ? '1' : '0');
}
return s;
}
#include "Bitaro.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
namespace {
const ll inf = 1e18 + 5;
int n, m, q, k;
vector<int> a, b, t, x;
vector<ll> c;
string s;
vector<vector<pair<int, ll> > > g;
map<pair<int, int>, int> idk, id;
void solve(int id, vector<int> &vr) // vrcholy, potom to zmenime na hrany
{
int pv = 0;
for (int j = 0; j < 9; j++) if (s[k + id * 9 + j] == '1') pv += (1 << j);
int st = (pv ? b[x[pv - 1]] : 0);
vector<ll> d(n, inf);
vector<int>p(n, -1);
set<pair<ll, pair<int, int> > > pq;
pq.insert({ 0, {st, -1} });
while (!pq.empty())
{
ll di = pq.begin()->first;
int u = pq.begin()->second.first;
int pi = pq.begin()->second.second;
pq.erase(pq.begin());
if (d[u] != inf) continue;
d[u] = di;
p[u] = pi;
for (pair<int, ll> v : g[u]) if (d[v.first] == inf && v.second != inf)
{
pq.insert({ d[u] + v.second, { v.first, u } });
}
}
int en = (id >= k ? t[id - k] : a[x[id]]);
while (en != st)
{
vr.push_back(en);
en = p[en];
}
vr.push_back(st);
if (pv) solve(pv - 1, vr);
}
}
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)
{
n = N, m = M, q = Q, k = K, a = A, b = B, c = C, t = T, x = X, s = S;
for (int i = 0; i < k; i++)
{
if (s[i] == '1') swap(a[x[i]], b[x[i]]);
idk[{a[x[i]], b[x[i]]}] = i;
c[x[i]] = inf;
}
g.assign(n, {});
for (int i = 0; i < m; i++) id[{a[i], b[i]}] = id[{b[i], a[i]}] = i, g[a[i]].push_back({ b[i], c[i] }), g[b[i]].push_back({ a[i], c[i] });
for (int i = 0; i < q; i++)
{
vector<int> vr;
solve(k + i, vr);
vector<int> e;
for (int j = 0; j + 1 < vr.size(); j++) e.push_back(id[{vr[j], vr[j + 1]}]);
answer(e);
}
}
Compilation message
Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < anc.size(); i++)
| ~~^~~~~~~~~~~~
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:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int j = 0; j + 1 < vr.size(); j++) e.push_back(id[{vr[j], vr[j + 1]}]);
| ~~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
88 ms |
8648 KB |
Wrong Answer [4] |
| 2 |
Halted |
0 ms |
0 KB |
- |
