QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506389#8642. Spy 3Max_s_xaM0 9ms6092kbC++178.3kb2024-08-05 17:08:002024-08-05 17:08:00

Judging History

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

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

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
Wrong Answer
time: 9ms
memory: 6092kb

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

A11111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

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

8
17135 13815 19828 8240 14190 2593 9175 14466
8
17135 13815 19828 8240 15826 8804 16633 7585
8
17135 13815 19828 4461 5746 11434 12510 15968
10
17135 13815 19828 4461 5746 11434 11567 10379 14255 15659
6
17135 13815 19828 4461 5746 11434
13
17135 13815 19828 4461 5746 11434 11567 10379 14255 16857 ...

Manager to Checker

0.00

result:

points 0.0
English 繁體中文 简体中文

Server Time: 2024-12-05 01:44:25 | OpenSource Project