QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506379#8642. Spy 3Max_s_xaM0 0ms0kbC++178.3kb2024-08-05 17:02:232024-08-05 17:02:23

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 17:02:23]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：0kb
查看
  • [2024-08-05 17:02:23]
  • 提交

Aoi

#include "Aoi.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

typedef long long ll;
typedef double lf;

using namespace std;

namespace
{

const int MAXN = 2e4 + 10;

int n, m;
bool avl[MAXN];

int fa[MAXN];
int Find(int k) { return k == fa[k] ? k : fa[k] = Find(fa[k]); }
inline void Union(int u, int v) { u = Find(u), v = Find(v); if (u != v) fa[u] = v; }

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; }
};
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];
int spt[MAXN], tot; bool 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++) fa[i] = i, dis[i] = 1e18, pth[i] = -1;
	for (int i = 0; i < K; i++) avl[X[i]] = 1;
	for (int i = 0; i < m; i++) A[i]++, B[i]++;
	for (int i = 0; i < m; i++)
		if (!avl[i]) Union(A[i], B[i]), e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i);

	for (int i = 1; i <= n; i++)
		if (fa[i] == i) Dijkstra(i, e, eval);
	// 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++)
		spt[++tot] = A[X[i]], spt[++tot] = B[X[i]];
	spt[++tot] = 1;
	for (int i = 0; i < Q; i++) spt[++tot] = T[i] + 1;
	stable_sort(spt + 1, spt + tot + 1, [&](int x, int y) { return Find(x) < Find(y); }), tot = unique(spt + 1, spt + tot + 1) - spt - 1;
	for (int i = 1; i <= tot; i++) isp[spt[i]] = 1;
	for (int l = 1, r = 0; l <= tot; l = r + 1)
	{
		while (r < tot && Find(spt[r + 1]) == Find(spt[l])) r++;
		Solve(spt[l], 0);
		top = 0, DFS(spt[l], 0, spt[l]);
	}

	for (int i = 0; i < K; i++)
	{
		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] = 1e18, 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';
	return ret;
}

// int main()
// {
// 	freopen("B.in", "r", stdin);
// 	freopen("B.out", "w", stdout);
// 	int n, m, q, k;
// 	cin >> n >> m;
// 	vector <int> A, B, T, X;
// 	vector <ll> C;
// 	for (int i = 1, u, v, w; i <= m; i++) cin >> u >> v >> w, A.push_back(u), B.push_back(v), C.push_back(w);
// 	cin >> q;
// 	for (int i = 1, x; i <= q; i++) cin >> x, T.push_back(x);
// 	cin >> k;
// 	for (int i = 1, x; i <= k; i++) cin >> x, X.push_back(x);
// 	cout << aoi(n, m, q, k, A, B, C, T, X) << endl;
// 	return 0;
// }
Source code, Language: C++17

Bitaro

#include "Bitaro.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

typedef long long ll;
typedef double lf;

using namespace std;

namespace
{

const int MAXN = 2e4 + 10;

int n, m;
bool avl[MAXN];

int fa[MAXN];
int Find(int k) { return k == fa[k] ? k : fa[k] = Find(fa[k]); }
inline void Union(int u, int v) { u = Find(u), v = Find(v); if (u != v) fa[u] = v; }

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; }
};
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];
int spt[MAXN], tot; bool isp[MAXN];
int st[MAXN], top;

vector <int> ed[MAXN];
int fr[MAXN], et = -1; vector <ll> val;
string ED;

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) spt[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)
{
	// cerr << "Bitaro\n";
	n = N, m = M, eval = C; ED = ret;
	for (int i = 1; i <= n; i++) fa[i] = i, dis[i] = 1e18, pth[i] = -1;
	for (int i = 0; i < K; i++) avl[X[i]] = 1;
	for (int i = 0; i < m; i++) A[i]++, B[i]++;
	for (int i = 0; i < m; i++)
		if (!avl[i]) Union(A[i], B[i]), e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i);

	for (int i = 1; i <= n; i++)
		if (fa[i] == i) Dijkstra(i, e, eval);
	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++)
		spt[++tot] = A[X[i]], spt[++tot] = B[X[i]];
	spt[++tot] = 1;
	for (int i = 0; i < Q; i++) spt[++tot] = T[i] + 1;
	stable_sort(spt + 1, spt + tot + 1, [&](int x, int y) { return Find(x) < Find(y); }), tot = unique(spt + 1, spt + tot + 1) - spt - 1;
	for (int i = 1; i <= tot; i++) isp[spt[i]] = 1;
	for (int l = 1, r = 0; l <= tot; l = r + 1)
	{
		while (r < tot && Find(spt[r + 1]) == Find(spt[l])) r++;
		Solve(spt[l], 0);
		top = 0, DFS(spt[l], 0, spt[l]);
	}

	for (int i = 0; i < K; i++)
	{
		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++) spt[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 = spt[u];
		}
		reverse(res.begin(), res.end());
		// for (auto x : res) cout << x << ' '; cout << '\n';
		answer(res);
	}
}



// int main()
// {
// 	freopen("B.in", "r", stdin);
// 	freopen("B.out", "w", stdout);
// 	int n, m, q, k;
// 	cin >> n >> m;
// 	vector <int> A, B, T, X;
// 	vector <ll> C;
// 	for (int i = 1, u, v, w; i <= m; i++) cin >> u >> v >> w, A.push_back(u), B.push_back(v), C.push_back(w);
// 	cin >> q;
// 	for (int i = 1, x; i <= q; i++) cin >> x, T.push_back(x);
// 	cin >> k;
// 	for (int i = 1, x; i <= k; i++) cin >> x, X.push_back(x);
// 	cout << aoi(n, m, q, k, A, B, C, T, X) << endl;
// 	return 0;
// }
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Instance #0 Runtime Error

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

Manager to Bitaro

WA

Bitaro to Manager

-1

Manager to Checker

0.00

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 02:04:25 | OpenSource Project