QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#707923 | #8642. Spy 3 | hhoppitree | 0 | 25ms | 8812kb | C++17 | 8.7kb | 2024-11-03 18:12:59 | 2024-11-03 18:13:00 |
Judging History
Aoi
#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;
vector<int> operator * (vector<int> x, int y) {
if (x.empty()) return {};
vector<int> tres(x.size());
for (int i = 0; i < (int)x.size(); ++i) {
tres[i] += x[i] * y;
if (i + 1 != (int)x.size()) {
tres[i + 1] += tres[i] >> 10;
tres[i] &= 1023;
}
}
while (tres.back() >= 1024) {
tres.push_back(tres.back() >> 10);
tres[tres.size() - 2] &= 1023;
}
return tres;
}
vector<int> operator + (vector<int> x, int y) {
if (!y) return x;
if (x.empty()) {
x = {0};
}
x[0] += y;
int r = 0;
while (r < (int)x.size() && x[r] >= 1024) {
x[r] -= 1024;
if (r == (int)x.size() - 1) x.push_back(0);
++x[r + 1];
}
return x;
}
string tr(vector<int> arr) {
string res;
for (int i = (int)arr.size() - 1; ~i; --i) {
for (int j = 9; ~j; --j) {
res += (char)(((arr[i] >> j) & 1) + '0');
}
}
while (!res.empty() && res[0] == '0') {
res = res.substr(1);
}
return res;
}
namespace Aoi {
const int N = 1e4 + 5;
vector< pair<int, long long> > G[N];
long long dis[N];
int pre[N];
vector<int> T[N];
int dep[N], clk[N];
void dfs(int x) {
for (auto v : T[x]) {
dep[v] = dep[x] + 1, dfs(v), clk[x] = min(clk[x], clk[v]);
}
}
int visit[N];
void mark(int x) {
while (x) {
visit[x] = 1;
x = pre[x];
}
}
int getLst(int x) {
while (x) {
if (visit[x]) return x;
x = pre[x];
}
return 0;
}
map< pair<int, int>, int> spe;
int getId(int x) {
while (x) {
if (spe.count({x, pre[x]})) {
return spe[{x, pre[x]}] + 1;
}
x = pre[x];
}
return 0;
}
string calc(vector< pair<int, int> > o) {
vector<int> res;
for (int i = (int)o.size() - 1; ~i; --i) {
res = res * o[i].first + o[i].second;
}
return tr(res);
}
string aoi(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o) {
for (int i = 0; i < m; ++i) {
G[ox[i]].push_back({oy[i], oz[i]});
G[oy[i]].push_back({ox[i], oz[i]});
}
for (int i = 1; i < n; ++i) {
dis[i] = 1e18;
}
priority_queue< pair<long long, int> > pq;
pq.push({0, 0});
while (!pq.empty()) {
long long D = -pq.top().first;
int x = pq.top().second;
pq.pop();
if (D != dis[x]) continue;
for (auto [v, w] : G[x]) {
long long nD = D + w;
if (nD < dis[v] || (nD == dis[v] && x < pre[v])) {
if (nD != dis[v]) pq.push({-nD, v});
dis[v] = nD, pre[v] = x;
}
}
}
for (int i = 0; i < n; ++i) clk[i] = q;
for (int i = 0; i < q; ++i) {
clk[qr[i]] = min(clk[qr[i]], i);
}
for (int i = 1; i < n; ++i) {
T[pre[i]].push_back(i);
}
dfs(0);
vector< pair<int, int> > res;
for (int i = 0; i < k; ++i) {
if (dep[ox[o[i]]] > dep[oy[o[i]]]) swap(ox[o[i]], oy[o[i]]);
res.push_back({q + 1, (pre[oy[o[i]]] == ox[o[i]] ? clk[oy[o[i]]] : q)});
spe[{ox[o[i]], oy[o[i]]}] = spe[{oy[o[i]], ox[o[i]]}] = i;
}
mark(qr[0]);
for (int i = 1; i < q; ++i) {
res.push_back({k + 1, getId(getLst(qr[i]))});
mark(qr[i]);
}
string ret = calc(res);
assert((int)ret.size() <= 1350);
return ret;
}
}
string aoi(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o) {
return Aoi::aoi(n, m, q, k, ox, oy, oz, qr, o);
}
Bitaro
#include <bits/stdc++.h>
#include "Bitaro.h"
using namespace std;
vector<int> operator / (vector<int> x, int y) {
vector<int> tres(x.size());
int now = 0;
for (int i = (int)x.size() - 1; ~i; --i) {
now = (now << 10) + x[i];
tres[i] = now / y;
now %= y;
}
while (!tres.empty() && !tres.back()) {
tres.pop_back();
}
return tres;
}
int operator % (vector<int> x, int y) {
vector<int> tres(x.size());
int now = 0;
for (int i = (int)x.size() - 1; ~i; --i) {
now = (now << 10) + x[i];
tres[i] = now / y;
now %= y;
}
return now;
}
vector<int> parse(string S) {
while (S.size() % 10) S = "0" + S;
vector<int> res(S.size() / 10);
for (int i = 0; i < (int)S.size(); i += 10) {
for (int j = 0; j < 10; ++j) {
res[(int)S.size() / 10 - 1 - i / 10] += (S[i + j] - '0') << (9 - j);
}
}
return res;
}
namespace Bitaro {
const int N = 1e4 + 5;
vector<int> apd[N];
int pre[N], det[N], dep[N], usd[N << 1];
vector< tuple<int, int, long long> > E;
long long dis[N];
vector< pair<int, int> > ts;
vector< pair<int, long long> > G[N];
vector<int> process(int n, vector<int> imp, int id) {
for (int i = 0; i < n; ++i) {
G[i].clear();
dis[i] = (i == 0 ? 0 : 1e18), pre[i] = 0;
}
for (auto [x, y, z] : E) {
G[x].push_back({y, z});
G[y].push_back({x, z});
}
for (auto x : imp) {
G[ts[x].first].push_back({ts[x].second, 0});
G[ts[x].second].push_back({ts[x].first, 0});
}
priority_queue< pair<long long, int> > pq;
pq.push({0, 0});
while (!pq.empty()) {
long long D = -pq.top().first;
int x = pq.top().second;
pq.pop();
if (D != dis[x]) continue;
for (auto [v, w] : G[x]) {
long long nD = D + w;
if (nD < dis[v] || (nD == dis[v] && x < pre[v])) {
if (nD != dis[v]) pq.push({-nD, v});
dis[v] = nD, pre[v] = x;
}
}
}
vector<int> path = {id};
int now = id;
while (now) {
path.push_back(pre[now]);
now = pre[now];
}
reverse(path.begin(), path.end());
for (int i = 1; i < (int)path.size(); ++i) {
det[path[i]] = path[i - 1];
dep[path[i]] = dep[path[i - 1]] + 1;
}
return path;
}
void bitaro(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o, string S) {
vector<int> val = parse(S);
map< pair<int, int>, int> zM;
for (int i = 0; i < k; ++i) {
int cl = val % (q + 1);
val = val / (q + 1);
apd[cl].push_back(i);
zM[{ox[o[i]], oy[o[i]]}] = zM[{oy[o[i]], ox[o[i]]}] = i;
}
map< pair<int, int>, int> M;
for (int i = 0; i < m; ++i) {
M[{ox[i], oy[i]}] = M[{oy[i], ox[i]}] = i;
}
for (int i = 0; i < k; ++i) {
usd[o[i]] = 1;
ts.push_back({ox[o[i]], oy[o[i]]});
}
for (int i = 0; i < m; ++i) {
if (!usd[i]) E.push_back({ox[i], oy[i], oz[i]});
}
for (int i = 0; i < q; ++i) {
vector<int> imp;
if (i) {
int id = val % (k + 1);
val = val / (k + 1);
if (id) {
--id;
if (dep[ox[o[id]]] < dep[oy[o[id]]]) {
swap(ox[o[id]], oy[o[id]]);
}
id = ox[o[id]];
while (id) {
if (usd[M[{id, det[id]}]]) {
imp.push_back(zM[{id, det[id]}]);
}
id = det[id];
}
}
}
for (auto x : apd[i]) {
imp.push_back(x);
}
vector<int> res = process(n, imp, qr[i]);
vector<int> ids;
for (int j = 0; j + 1 < (int)res.size(); ++j) {
ids.push_back(M[{res[j], res[j + 1]}]);
}
answer(ids);
}
}
}
void bitaro(int n, int m, int q, int k, vector<int> ox, vector<int> oy, vector<long long> oz, vector<int> qr, vector<int> o, string S) {
Bitaro::bitaro(n, m, q, k, ox, oy, oz, qr, o, S);
}
詳細信息
Test #1:
score: 100
Accepted
time: 25ms
memory: 8812kb
Manager to Aoi
200 19900 13 70 985302938314 120 174 18964037101 18 153 170196070829 45 129 323777973024 62 198 689223413645 88 133 457404464825 19 57 803409835578 22 187 662331177910 18 31 529437059733 161 182 637731822589 109 131 32831735773 109 191 875742441191 43 78 135479410688 56 60 19000632823 44 143 6823771...
Aoi to Manager
A11010111100100001101010000011010100001011000001101000010000100101000010111110001101001010110100011110111110100000000010010111010000110101001011101001000110100100001001001100001100110110011110110100010100010101110101101000011111010001000100100110100101010111101101001111001011101111111000100100101110...
Manager to Bitaro
200 19900 13 70 985302938314 120 174 18964037101 18 153 170196070829 45 129 323777973024 62 198 689223413645 88 133 457404464825 19 57 803409835578 22 187 662331177910 18 31 529437059733 161 182 637731822589 109 131 32831735773 109 191 875742441191 43 78 135479410688 56 60 19000632823 44 143 6823771...
Bitaro to Manager
4 17135 3534 4830 14466 1 11921 2 17135 9906 4 17135 3534 18777 907 6 18033 13659 9145 14255 10379 11567 7 11921 7585 5782 2139 15549 19315 13987 2 17135 13815 5 17135 13815 8201 7265 15719 4 17135 3534 4830 9175 4 11921 7585 5782 8018 2 18033 13659 4 11921 7585 10922 14444 5 468 273 10532 11483 845...
Manager to Checker
1.00
result:
points 1.0
Test #2:
score: 100
Accepted
time: 1ms
memory: 4556kb
Manager to Aoi
6 7 0 5 839719370667 2 4 244076065937 1 5 337346113825 2 3 716558559511 1 4 837188452057 0 3 661778933008 1 3 678360389380 5 2 3 1 5 4 7 4 2 0 6 1 5 3
Aoi to Manager
A111111000110101101100111010001F
Manager to Bitaro
6 7 0 5 -1 2 4 -1 1 5 -1 2 3 -1 1 4 -1 0 3 -1 1 3 -1 5 2 3 1 5 4 7 4 2 0 6 1 5 3 A111111000110101101100111010001F
Bitaro to Manager
2 5 3 1 5 2 0 2 1 0 3 5 3 1 F
Manager to Checker
1.00
result:
points 1.0
Test #3:
score: 0
Instance #1 Time Limit Exceeded
Manager to Aoi
10000 19480 2933 9484 1000000000000 2567 9405 1000000000000 5263 6064 1000000000000 1453 8911 1000000000000 2445 8695 1000000000000 5686 7074 1000000000000 5031 5441 1000000000000 253 5144 1000000000000 8087 8704 1000000000000 263 3499 1000000000000 5200 8741 1000000000000 5764 8908 1000000000000 20...
Aoi to Manager
A11100111101111010010100000101011100000010010110110001001110011110110000110111110011101110110000100011011011001011010101101001010110010000011100000100011011100100000111110011011101101011011000010111101100110100100110101111110000001000111010010101010010010001100000101011100101001100000101000011110011...
Manager to Bitaro
10000 19480 2933 9484 1000000000000 2567 9405 1000000000000 5263 6064 1000000000000 1453 8911 1000000000000 2445 8695 1000000000000 5686 7074 1000000000000 5031 5441 1000000000000 253 5144 1000000000000 8087 8704 1000000000000 263 3499 1000000000000 5200 8741 1000000000000 5764 8908 1000000000000 20...
Bitaro to Manager
Manager to Checker
0.00