Submission #1283359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283359		arashmemar	Spy 3 (JOI24_spy3)	C++20	0 / 100	1096 ms	2252 KiB

Aoi

#include <bits/stdc++.h>
#include "Aoi.h"

using namespace std;

const int maxn = 2e4 + 100;
const long long int inf = 1e16;

bool dac[maxn];
std::vector <std::pair <int, long long int>> ne[maxn];
vector <pair <int, pair <long long int, int > > > nee[maxn];

std::pair <int, long long int> upd[maxn];

long long int dis[maxn];

std::set <std::pair <long long int, int>> dij;

std::string aoi(int n, int m, int q, int k, std::vector<int> a,
                std::vector<int> b, std::vector<long long> C,
                std::vector<int> t, std::vector<int> x) 
{
	for (int i = 0;i < k;i++)
	{
		dac[x[i]] = 1;
		int v = a[i], u = b[i];
		long long int c = C[i];
		nee[v].push_back({u, {c, i}});
		nee[u].push_back({v, {c, i}});
	}
	for (int i = 0;i < m;i++)
	{
		int v = a[i], u = b[i];
		long long int c = C[i];
		if (dac[i])
		{
			c = inf;
		}
		ne[v].push_back({u, c});
		ne[u].push_back({v, c});
	}

	for (int i = 1;i < n;i++)
	{
		dis[i] = inf * 600;
		dij.insert({inf * 600, i});
	}
	dis[0] = 0;
	dij.insert({0, 0});

	int cnt = k;

	while (dij.size())
	{
		int v = (*dij.begin()).second;
		dij.erase(dij.begin());
		if (v)
		{
			int u = upd[v].first;
			long long int c = upd[v].second;
			nee[v].push_back({u, {c, cnt}});
			nee[u].push_back({v, {c, cnt++}});
		}

		for (auto o : ne[v])
		{
			int u = o.first;
			long long int c = o.second;

			if (dis[u] > dis[v] + c)
			{
				dij.erase({dis[u], u});
				dis[u] = dis[v] + c;
				dij.insert({dis[u], u});
				upd[u] = {v, c};
			}
		}
	}

	string s;

	for (int i = 0;i < cnt;i++)
	{
		s += '0';
	}

	for (int i = 1;i < n;i++)
	{
		dis[i] = inf * 600;
		dij.insert({inf * 600, i});
	}
	dis[0] = 0;
	dij.insert({0, 0});

	while(dij.size())
	{
		int v = (*dij.begin()).second;
		if (v)
		{
			s[upd[v].first] = '1';
		}

		for (auto o : nee[v])
		{
			int u = o.first, ind = o.second.second;
			long long int c = o.second.first;

			if (dis[u] > dis[v] + c)
			{
				dij.erase({dis[u], u});
				dis[u] = dis[v] + c;
				dij.insert({dis[u], u});
				upd[u].first = ind;
			}
		}
	}
	return s;
}

Bitaro

#include <bits/stdc++.h>
#include "Bitaro.h"

using namespace std;

const int maxn = 2e4 + 100;
const long long int inf = 1e16;

bool dac[maxn], mark[maxn];

int ac[maxn];

std::vector <std::pair <int, long long int>> ne[maxn];
std::vector <int> ne2[maxn], p, ans[maxn];

std::vector <std::pair <int, int>> es;

std::pair <int, long long int> upd[maxn];

long long int dis[maxn];

std::set <std::pair <long long int, int>> dij;

void dfs(int v)
{
	mark[v] = 1;

	if (ac[v])
	{
		ans[ac[v]] = p;
	}

	for (auto u : ne2[v])
	{
		if (mark[u])
		{
			continue;
		}
		p.push_back(u);
		dfs(u);
		p.pop_back();
	}
	return ;
}

void bitaro(int n, int m, int q, int k, std::vector<int> a,
                std::vector<int> b, std::vector<long long> C,
                std::vector<int> t, std::vector<int> x, string s) 
{
	for (int i = 0;i < k;i++)
	{
		dac[x[i]] = 1;
		int v = a[i], u = b[i];
		long long int c = C[i];
		es.push_back({v, u});
	}
	for (int i = 0;i < m;i++)
	{
		int v = a[i], u = b[i];
		long long int c = C[i];
		if (dac[i])
		{
			c = inf;
		}
		ne[v].push_back({u, c});
		ne[u].push_back({v, c});
	}

	for (int i = 1;i < n;i++)
	{
		dis[i] = inf * 600;
		dij.insert({inf * 600, i});
	}
	dis[0] = 0;
	dij.insert({0, 0});

	int cnt = k;

	while (dij.size())
	{
		int v = (*dij.begin()).second;
		dij.erase(dij.begin());
		if (v)
		{
			int u = upd[v].first;
			long long int c = upd[v].second;
			es.push_back({v, u});
		}

		for (auto o : ne[v])
		{
			int u = o.first;
			long long int c = o.second;

			if (dis[u] > dis[v] + c)
			{
				dij.erase({dis[u], u});
				dis[u] = dis[v] + c;
				dij.insert({dis[u], u});
				upd[u] = {v, c};
			}
		}
	}

	for (int i = 0;i < s.size();i++)
	{
		if (s[i] == '1')
		{
			int v = es[i].first, u = es[i].second;
			ne2[v].push_back(u);
			ne2[u].push_back(v);
		}
	}

	for (int i = 0;i < q;i++)
	{
		ac[t[i]] = i + 1;
	}

	p.push_back(0);
	dfs(0);

	for (int i = 1;i <= q;i++)
	{
		answer(ans[i]);
	}
	return ;
}

• Subtask 1: 0 / 100