Submission #978214

#	Time	Username	Problem	Language	Result	Execution time	Memory
978214		model_code	Spy 3 (JOI24_spy3)	C++17	100 / 100	125 ms	6760 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;

namespace
{
	struct edge
	{
		int to, id;
		long long dist;
		edge(int to, int id, long long dist) : to(to), id(id), dist(dist) {}
	};
	class BigInt
	{
		const long long base = 1ll << 32;
		vector<long long> v;
		void update()
		{
			for (int i = 0; i < v.size(); i++)
			{
				long long r = v[i] / base;
				if (r == 0)
					continue;
				v[i] %= base;
				if (i == v.size() - 1)
				{
					v.push_back(r);
				}
				else
				{
					v[i + 1] += r;
				}
			}
		}

	public:
		BigInt &operator+=(const long long t)
		{
			if (v.empty())
			{
				v.push_back(t);
			}
			else
			{
				v.front() += t;
			}
			update();
			return *this;
		}
		BigInt &operator*=(const long long t)
		{
			for (int i = 0; i < v.size(); i++)
			{
				v[i] *= t;
			}
			update();
			return *this;
		}
		BigInt &operator/=(const long long t)
		{
			long long m = 0;
			for (int i = v.size() - 1; i >= 0; i--)
			{
				m *= base;
				v[i] += m;
				m = v[i] % t;
				v[i] /= t;
			}
			return *this;
		}
		long long operator%(const long long t)
		{
			long long m = 0;
			for (int i = v.size() - 1; i >= 0; i--)
			{
				m *= base;
				m += v[i];
				m %= t;
			}
			return m;
		}
		string encode(int d)
		{
			string t;
			for (int i = 0; i < d; i++)
			{
				int k = i / 32;
				if (k >= v.size())
				{
					t += '0';
				}
				else
				{
					int m = i % 32;
					t += '0' + ((v[k] >> m) & 1);
				}
			}
			return t;
		}
	};
} // namespace

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)
{
	vector<vector<edge>> edges(N);
	for (int i = 0; i < M; i++)
	{
		edges[A[i]].emplace_back(B[i], i, C[i]);
		edges[B[i]].emplace_back(A[i], i, C[i]);
	}
	vector<long long> dist(N, -1);
	priority_queue<pair<long long, int>, vector<pair<long long, int>>,
				   greater<pair<long long, int>>>
		pq;
	pq.push({0, 0});
	while (!pq.empty())
	{
		int x = pq.top().second;
		long long d = pq.top().first;
		pq.pop();
		if (dist[x] != -1)
		{
			continue;
		}
		dist[x] = d;
		for (edge e : edges[x])
		{
			pq.push({d + e.dist, e.to});
		}
	}
	vector<int> map_edges(M, -1);
	for (int i = 0; i < K; i++)
	{
		map_edges[X[i]] = i;
	}
	vector<int> first_query_num(K, Q); // ãã‚Œãžã‚Œã®éš ã•ã‚Œã¦ã„ã‚‹è¾ºã«ã¤ã„ã¦ï¼Œãã®è¾ºã‚’é€šéŽã™ã‚‹æœ€åˆã®ã‚¯ã‚¨ãƒªç•ªå·
	vector<int> last_edge_num(Q, K);   // ãã‚Œãžã‚Œã®ã‚¯ã‚¨ãƒªã«ã¤ã„ã¦ï¼Œãã‚Œä»¥å‰ã®ã‚¯ã‚¨ãƒªã§é€šã£ãŸè¾ºã®ã†ã¡æœ€ã‚‚æœ€å¾Œã«é€šã‚‹ï¼ˆéš ã•ã‚ŒãŸï¼‰è¾ºã®ç•ªå·
	for (int i = 0; i < Q; i++)
	{
		int p = T[i];
		while (p != 0)
		{
			for (edge e : edges[p])
			{
				if (dist[e.to] + e.dist == dist[p])
				{
					int m_id = map_edges[e.id];
					if (m_id != -1)
					{
						if (last_edge_num[i] == K &&
							first_query_num[m_id] != Q)
						{
							last_edge_num[i] = m_id;
						}
						if (first_query_num[m_id] == Q)
						{
							first_query_num[m_id] = i;
						}
					}
					p = e.to;
					break;
				}
			}
		}
	}
	string s;
	BigInt bi;
	for (int i = 0; i < K; i++)
	{
		bi *= Q + 1;
		bi += first_query_num[i];
	}
	for (int i = 1; i < Q; i++)
	{
		bi *= K + 1;
		bi += last_edge_num[i];
	}
	return bi.encode(1350);
}

Bitaro

#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;

namespace
{
	struct edge
	{
		int to, id;
		long long dist;
		edge(int to, int id, long long dist) : to(to), id(id), dist(dist) {}
	};
	class BigInt
	{
		const long long base = 1ll << 32;
		vector<long long> v;
		void update()
		{
			for (int i = 0; i < v.size(); i++)
			{
				long long r = v[i] / base;
				if (r == 0)
					continue;
				v[i] %= base;
				if (i == v.size() - 1)
				{
					v.push_back(r);
				}
				else
				{
					v[i + 1] += r;
				}
			}
		}

	public:
		BigInt &operator+=(const long long t)
		{
			if (v.empty())
			{
				v.push_back(t);
			}
			else
			{
				v.front() += t;
			}
			update();
			return *this;
		}
		BigInt &operator*=(const long long t)
		{
			for (int i = 0; i < v.size(); i++)
			{
				v[i] *= t;
			}
			update();
			return *this;
		}
		BigInt &operator/=(const long long t)
		{
			long long m = 0;
			for (int i = v.size() - 1; i >= 0; i--)
			{
				m *= base;
				v[i] += m;
				m = v[i] % t;
				v[i] /= t;
			}
			return *this;
		}
		long long operator%(const long long t)
		{
			long long m = 0;
			for (int i = v.size() - 1; i >= 0; i--)
			{
				m *= base;
				m += v[i];
				m %= t;
			}
			return m;
		}
		string encode(int d)
		{
			string t;
			for (int i = 0; i < d; i++)
			{
				int k = i / 32;
				if (k >= v.size())
				{
					t += '0';
				}
				else
				{
					int m = i % 32;
					t += '0' + ((v[k] >> m) & 1);
				}
			}
			return t;
		}
	};
	BigInt decode(string s, int d)
	{
		BigInt bi;
		for (int i = d - 1; i >= 0; i--)
		{
			bi *= 2;
			if (s[i] == '1')
			{
				bi += 1;
			}
		}
		return bi;
	}
} // namespace

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)
{
	BigInt bi = decode(s, 1350);
	vector<int> first_query_num(K, Q);
	vector<int> last_edge_num(Q, K);
	for (int i = Q - 1; i >= 1; i--)
	{
		last_edge_num[i] = bi % (K + 1);
		bi /= K + 1;
	}
	for (int i = K - 1; i >= 0; i--)
	{
		first_query_num[i] = bi % (Q + 1);
		bi /= Q + 1;
	}
	vector<vector<int>> answers(Q);
	for (int i = 0; i < Q; i++)
	{
		vector<vector<edge>> edges(N);
		for (int j = 0; j < K; j++)
		{
			if (first_query_num[j] == i)
			{
				C[X[j]] = 1;
			}
			else
			{
				C[X[j]] = 20'000'000'000'000'000;
			}
		}
		for (int j = 0; j < M; j++)
		{
			edges[A[j]].emplace_back(B[j], j, C[j]);
			edges[B[j]].emplace_back(A[j], j, C[j]);
		}
		vector<long long> dist(N, -1);
		priority_queue<pair<long long, int>, vector<pair<long long, int>>,
					   greater<pair<long long, int>>>
			pq;
		int start = 0;
		if (last_edge_num[i] != K)
		{
			int q = first_query_num[last_edge_num[i]];
			for (int j = 0;; j++)
			{
				answers[i].push_back(answers[q][j]);
				start ^= A[answers[q][j]] ^ B[answers[q][j]];
				if (answers[q][j] == X[last_edge_num[i]])
				{
					break;
				}
			}
		}
		pq.emplace(0, start);
		while (!pq.empty())
		{
			int x = pq.top().second;
			long long d = pq.top().first;
			pq.pop();
			if (dist[x] != -1)
			{
				continue;
			}
			dist[x] = d;
			for (edge e : edges[x])
			{
				pq.emplace(d + e.dist, e.to);
			}
		}
		int p = T[i];
		vector<int> v;
		while (p != start)
		{
			for (edge e : edges[p])
			{
				if (dist[e.to] + e.dist == dist[p])
				{
					v.push_back(e.id);
					p = e.to;
					break;
				}
			}
		}
		reverse(v.begin(), v.end());
		for (int t : v)
		{
			answers[i].push_back(t);
		}
		answer(answers[i]);
	}
}

Compilation message (stderr)

Aoi.cpp: In member function 'void {anonymous}::BigInt::update()':
Aoi.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    for (int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
Aoi.cpp:25:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if (i == v.size() - 1)
      |         ~~^~~~~~~~~~~~~~~
Aoi.cpp: In member function '{anonymous}::BigInt& {anonymous}::BigInt::operator*=(long long int)':
Aoi.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for (int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
Aoi.cpp: In member function 'std::string {anonymous}::BigInt::encode(int)':
Aoi.cpp:88:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     if (k >= v.size())
      |         ~~^~~~~~~~~~~

Bitaro.cpp: In member function 'void {anonymous}::BigInt::update()':
Bitaro.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    for (int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
Bitaro.cpp:25:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if (i == v.size() - 1)
      |         ~~^~~~~~~~~~~~~~~
Bitaro.cpp: In member function '{anonymous}::BigInt& {anonymous}::BigInt::operator*=(long long int)':
Bitaro.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for (int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
Bitaro.cpp: In member function 'std::string {anonymous}::BigInt::encode(int)':
Bitaro.cpp:88:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     if (k >= v.size())
      |         ~~^~~~~~~~~~~

• Subtask 1: 100 / 100