QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #506504 | #8642. Spy 3 | Max_s_xaM | 0 | 14ms | 6580kb | C++17 | 6.5kb | 2024-08-05 18:23:39 | 2024-08-05 18:23:40 |
Judging History
Aoi
#include "Aoi.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
typedef long long ll;
typedef __int128 LL;
typedef double lf;
using namespace std;
namespace
{
const int MAXN = 2e4 + 10;
int n, m;
bool avl[MAXN];
vector <pair <int, int>> e[MAXN], tr[MAXN];
vector <ll> eval;
LL dis[MAXN]; bool vis[MAXN];
int pth[MAXN];
struct Node
{
LL dis; int x;
bool operator < (const Node &u) const { return dis == u.dis ? x < u.x : dis > u.dis; }
};
priority_queue <Node> q;
inline void Dijkstra(int s, vector <pair <int, int>> *e, vector <ll> &eval)
{
dis[s] = 0, q.push(Node{dis[s], s});
while (!q.empty())
{
int u = q.top().x; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : e[u])
if (dis[v] > dis[u] + eval[w])
{
dis[v] = dis[u] + eval[w], pth[v] = w;
q.push(Node{dis[v], v});
}
}
}
bool ist[MAXN], isp[MAXN];
int st[MAXN], top;
vector <int> ed[MAXN];
int fr[MAXN], et = -1; vector <ll> val;
inline bool Solve(int u, int ff)
{
int cnt = isp[u];
for (auto [v, w] : e[u])
if (v != ff) cnt += Solve(v, u);
if (cnt > 1) isp[u] = 1;
return cnt > 0;
}
inline void DFS(int u, int ff, int hd)
{
if (isp[u] && ff)
{
et++;
ll sum = 0;
while (top) sum += eval[st[top]], ed[et].push_back(st[top--]);
fr[et] = u, val.push_back(sum), tr[hd].emplace_back(u, et), tr[u].emplace_back(hd, et);
hd = u;
}
for (auto [v, w] : e[u])
if (v != ff)
{
st[++top] = w, DFS(v, u, hd);
if (top) top--;
}
}
}
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)
{
n = N, m = M, eval = C;
for (int i = 1; i <= n; i++) dis[i] = 1e24, pth[i] = -1;
for (int i = 0; i < K; i++) eval[X[i]] = 3e16;
for (int i = 0; i < m; i++) A[i]++, B[i]++;
for (int i = 0; i < m; i++) e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i);
Dijkstra(1, e, eval), eval = C;
// for (int i = 1; i <= n; i++) cout << dis[i] << ' '; cout << '\n';
for (int i = 1; i <= n; i++)
if (~pth[i]) ist[pth[i]] = 1;
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 0; i < m; i++)
if (ist[i]) e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i);
// for (int i = 0; i < m; i++)
// if (ist[i]) cout << i << ' '; cout << "\n";
for (int i = 0; i < K; i++) isp[A[X[i]]] = isp[B[X[i]]] = 1;
isp[1] = 1;
for (int i = 0; i < Q; i++) isp[T[i] + 1] = 1;
Solve(1, 0), DFS(1, 0, 1);
for (int i = 0; i < K; i++)
{
if (ist[X[i]]) continue;
et++, ed[et].push_back(X[i]), fr[et] = A[X[i]];
val.push_back(C[X[i]]), tr[A[X[i]]].emplace_back(B[X[i]], et), tr[B[X[i]]].emplace_back(A[X[i]], et);
}
// for (int i = 1; i <= n; i++)
// {
// cout << i - 1 << ":\n";
// for (auto [v, w] : tr[i]) cout << v - 1 << ' ' << val[w] << '\n';
// }
// for (int i = 0; i <= et; i++)
// {
// cout << "Fr: " << fr[i] - 1 << " Val: " << val[i] << " Edge: ";
// for (auto x : ed[i]) cout << x << ' '; cout << "\n";
// }
for (int i = 1; i <= n; i++) dis[i] = 1e24, vis[i] = 0, pth[i] = -1;
Dijkstra(1, tr, val);
// for (int i = 1; i <= n; i++) cout << dis[i] << '\n';
string ret; ret.resize(et + 1);
for (int i = 0; i <= et; i++) ret[i] = '0';
for (int i = 1; i <= n; i++)
if (~pth[i]) ret[pth[i]] = '1';
// cout << ret << '\n';
// cerr << "##\n";
return ret;
}
Bitaro
#include "Bitaro.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
typedef long long ll;
typedef double lf;
typedef __int128 LL;
using namespace std;
namespace
{
const int MAXN = 2e4 + 10;
int n, m;
bool avl[MAXN];
string ED;
vector <pair <int, int>> e[MAXN], tr[MAXN];
vector <ll> eval;
LL dis[MAXN]; bool vis[MAXN];
int pth[MAXN];
struct Node
{
LL dis; int x;
bool operator < (const Node &u) const { return dis == u.dis ? x < u.x : dis > u.dis; }
};
priority_queue <Node> q;
inline void Dijkstra(int s, vector <pair <int, int>> *e, vector <ll> &eval)
{
dis[s] = 0, q.push(Node{dis[s], s});
while (!q.empty())
{
int u = q.top().x; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : e[u])
if (dis[v] > dis[u] + eval[w])
{
dis[v] = dis[u] + eval[w], pth[v] = w;
q.push(Node{dis[v], v});
}
}
}
bool ist[MAXN], isp[MAXN];
int st[MAXN], top;
vector <int> ed[MAXN];
int fr[MAXN], et = -1; vector <ll> val;
inline bool Solve(int u, int ff)
{
int cnt = isp[u];
for (auto [v, w] : e[u])
if (v != ff) cnt += Solve(v, u);
if (cnt > 1) isp[u] = 1;
return cnt > 0;
}
inline void DFS(int u, int ff, int hd)
{
if (isp[u] && ff)
{
et++;
ll sum = 0;
while (top) sum += eval[st[top]], ed[et].push_back(st[top--]);
fr[et] = u, val.push_back(sum);
if (ED[et] == '1') tr[hd].emplace_back(u, et), tr[u].emplace_back(hd, et);
hd = u;
}
for (auto [v, w] : e[u])
if (v != ff)
{
st[++top] = w, DFS(v, u, hd);
if (top) top--;
}
}
inline void DFS2(int u, int ff)
{
for (auto [v, w] : tr[u])
if (v != ff) st[v] = u, pth[v] = w, DFS2(v, u);
}
}
void bitaro(int N, int M, int Q, int K, vector <int> A, vector <int> B, vector <ll> C, vector <int> T, vector <int> X, string ret)
{
n = N, m = M, eval = C; ED = ret;
for (int i = 1; i <= n; i++) dis[i] = 1e24, pth[i] = -1;
for (int i = 0; i < K; i++) eval[X[i]] = 3e16;
for (int i = 0; i < m; i++) A[i]++, B[i]++;
for (int i = 0; i < m; i++) e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i);
Dijkstra(1, e, eval), eval = C;
for (int i = 1; i <= n; i++)
if (~pth[i]) ist[pth[i]] = 1;
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 0; i < m; i++)
if (ist[i]) e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i);
for (int i = 0; i < K; i++) isp[A[X[i]]] = isp[B[X[i]]] = 1;
isp[1] = 1;
for (int i = 0; i < Q; i++) isp[T[i] + 1] = 1;
Solve(1, 0), DFS(1, 0, 1);
for (int i = 0; i < K; i++)
{
if (ist[X[i]]) continue;
et++, ed[et].push_back(X[i]), fr[et] = A[X[i]];
val.push_back(C[X[i]]);
if (ED[et] == '1') tr[A[X[i]]].emplace_back(B[X[i]], et), tr[B[X[i]]].emplace_back(A[X[i]], et);
}
// for (int i = 1; i <= n; i++)
// {
// cerr << i - 1 << ":\n";
// for (auto [v, w] : tr[i]) cerr << v - 1 << ' ' << val[w] << '\n';
// }
for (int i = 1; i <= n; i++) st[i] = 0;
DFS2(1, 0);
for (int i = 0; i < Q; i++)
{
int u = T[i] + 1;
vector <int> res;
while (u != 1)
{
if (fr[pth[u]] == u)
for (auto x : ed[pth[u]]) res.push_back(x);
else
for (int i = ed[pth[u]].size() - 1; ~i; i--) res.push_back(ed[pth[u]][i]);
u = st[u];
}
reverse(res.begin(), res.end());
// for (auto x : res) cout << x << ' '; cout << '\n';
answer(res);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 6116kb
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
A11111111111111111111111111111111111111111111111111111111111101111111111111101111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100...
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: 0ms
memory: 5272kb
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
A1111100F
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 A1111100F
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
Wrong Answer
time: 14ms
memory: 6580kb
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
A11011111011101111111000111101111110110111000111101101010111110111110111111101101110111011101101111111011011001111110101111111011101111111001110110010111011001111001110110111111011111011011111010110101111101101010110111110111101110110111000111101111111001111111110111000111101111001011111111111110110...
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
97 3060 18368 7726 17142 5985 14532 2640 14471 7194 19306 3061 5161 16214 7373 11764 3296 12515 7042 6222 1690 5352 14008 12642 6794 293 10981 6900 13148 16790 5580 4232 18515 15247 861 11590 7841 2964 16468 12973 6217 15383 9794 11429 6053 10375 9579 5235 14687 18082 1447 14862 5411 11567 14828 447...
Manager to Checker
0.00
result:
points 0.0