oj.uz

Submission #659764

# Submission time Handle Problem Language Result Execution time Memory
659764 2022-11-19T08:53:02 Z ymm From Hacks to Snitches (BOI21_watchmen) C++17
5 / 100
 98 ms 33252 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 250'010;
const int L = 1600;
bool has_watch[N];
int watch_size[N];
int watch_ind[N];
int watch_guard[N];

int watch_size_list[L];

int n, m, k;

int *nxt[L][L];

void calc_nxt(int step, int size)
{
	if (nxt[step][size])
		return;
	nxt[step][size] = new int[size];
	int cnt = 0;
	for (int beg=0; cnt < size; ++beg) {
		vector<pii> vec;
		int x = beg;
		do {
			while (vec.size() && vec.front().first > x)
				vec.pop_back();
			nxt[step][size][x] = vec.size()?
					cnt - vec.back().second:
					-1;
			vec.push_back({x, cnt});
			++cnt;
			x = x-step;
			x = x<0?x+size:x;
		} while (x != beg);
	}
}

vector<int> A[N];
int norm_dis[N];

void bfs(int s)
{
	memset(norm_dis, -1, sizeof(norm_dis));
	vector<int> q = {s};
	Loop (i,0,q.size()) {
		int v = q[i];
		for (int u : A[v]) {
			if (norm_dis[u] != -1)
				continue;
			norm_dis[u] = norm_dis[v] + 1;
			q.push_back(u);
		}
	}
}

vector<ll> dis[N];

void upS(int from, int v, ll d, set<tuple<ll,int,int>> &Set)
{
	int md = has_watch[v]? d % watch_size[v]: 0;
	if (d >= dis[v][md])
		return;
	if (has_watch[v] && md == watch_ind[v])
		return;
	if (has_watch[from] && has_watch[v] && watch_guard[from] == watch_guard[v] && watch_ind[from] == md && (watch_ind[v] == md-1 || watch_ind[v] == md+watch_size[v]-1))
		return;
	Set.erase ({dis[v][md]+norm_dis[v], md, v});
	dis[v][md] = d;
	Set.insert({dis[v][md]+norm_dis[v], md, v});
}

void up3(int v, int u, ll d, set<tuple<ll,int,int>> &Set)
{
	int step = watch_size[v];
	int size = watch_size[u];
	int x = (d + size - watch_ind[u]) % size;
	++d;
	for (;;) {
		upS(v, u, d, Set);
		ll cnt = nxt[step][size][x];
		if (cnt == -1)
			break;
		d += cnt*step;
		x = (x + cnt*step) % size;
	}
}

ll dij(int s, int t)
{
	set<tuple<ll,int,int>> Set;
	Loop (i,0,N)
		dis[i] = vector<ll>(has_watch[i]?watch_size[i]:1, (ll)1e17);
	dis[s][0] = 0;
	Set.insert({dis[s][0]+norm_dis[s], 0, s});
	while (Set.size()) {
		auto [dard, md, v] = *Set.begin();
		Set.erase(Set.begin());
		ll d = dis[v][md];
		if (v == t)
			return d;
		upS(v, v, d+1, Set);
		for (int u : A[v]) {
			if (has_watch[u] && has_watch[v]) {
				up3(v, u, d, Set);
			} else if (has_watch[u]) {
				upS(v, u, d+1, Set);
				int wait = watch_ind[u] - d%watch_size[u];
				wait = wait<0?wait+watch_size[u]:wait;
				upS(v, u, d+1+wait, Set);
			} else {
				upS(v, u, d+1, Set);
			}
		}
	}
	return -1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop (i,0,m) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	cin >> k;
	Loop (i,0,k) {
		int l;
		cin >> l;
		watch_size_list[i] = l;
		Loop (j,0,l) {
			int v;
			cin >> v;
			--v;
			watch_size[v] = l;
			watch_ind[v] = j;
			has_watch[v] = 1;
			watch_guard[v] = i;
		}
	}
	Loop (i,0,k) Loop (j,0,k)
		calc_nxt(watch_size_list[i], watch_size_list[j]);
	bfs(n-1);
	ll ans = dij(0, n-1);
	if (ans == -1)
		cout << "impossible\n";
	else
		cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22444 KB Output is correct
2 Correct 92 ms 26216 KB Output is correct
3 Correct 94 ms 25812 KB Output is correct
4 Correct 68 ms 26144 KB Output is correct
5 Correct 19 ms 21156 KB Output is correct
6 Correct 72 ms 25808 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 22476 KB Output is correct
2 Correct 98 ms 26120 KB Output is correct
3 Correct 86 ms 25904 KB Output is correct
4 Correct 73 ms 26188 KB Output is correct
5 Correct 19 ms 21040 KB Output is correct
6 Correct 70 ms 25848 KB Output is correct
7 Runtime error 50 ms 33252 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 22476 KB Output is correct
2 Correct 98 ms 26120 KB Output is correct
3 Correct 86 ms 25904 KB Output is correct
4 Correct 73 ms 26188 KB Output is correct
5 Correct 19 ms 21040 KB Output is correct
6 Correct 70 ms 25848 KB Output is correct
7 Runtime error 50 ms 33252 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 22476 KB Output is correct
2 Correct 98 ms 26120 KB Output is correct
3 Correct 86 ms 25904 KB Output is correct
4 Correct 73 ms 26188 KB Output is correct
5 Correct 19 ms 21040 KB Output is correct
6 Correct 70 ms 25848 KB Output is correct
7 Runtime error 50 ms 33252 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22444 KB Output is correct
2 Correct 92 ms 26216 KB Output is correct
3 Correct 94 ms 25812 KB Output is correct
4 Correct 68 ms 26144 KB Output is correct
5 Correct 19 ms 21156 KB Output is correct
6 Correct 72 ms 25808 KB Output is correct
7 Correct 34 ms 22476 KB Output is correct
8 Correct 98 ms 26120 KB Output is correct
9 Correct 86 ms 25904 KB Output is correct
10 Correct 73 ms 26188 KB Output is correct
11 Correct 19 ms 21040 KB Output is correct
12 Correct 70 ms 25848 KB Output is correct
13 Runtime error 50 ms 33252 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22444 KB Output is correct
2 Correct 92 ms 26216 KB Output is correct
3 Correct 94 ms 25812 KB Output is correct
4 Correct 68 ms 26144 KB Output is correct
5 Correct 19 ms 21156 KB Output is correct
6 Correct 72 ms 25808 KB Output is correct
7 Correct 34 ms 22476 KB Output is correct
8 Correct 98 ms 26120 KB Output is correct
9 Correct 86 ms 25904 KB Output is correct
10 Correct 73 ms 26188 KB Output is correct
11 Correct 19 ms 21040 KB Output is correct
12 Correct 70 ms 25848 KB Output is correct
13 Runtime error 50 ms 33252 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22444 KB Output is correct
2 Correct 92 ms 26216 KB Output is correct
3 Correct 94 ms 25812 KB Output is correct
4 Correct 68 ms 26144 KB Output is correct
5 Correct 19 ms 21156 KB Output is correct
6 Correct 72 ms 25808 KB Output is correct
7 Correct 34 ms 22476 KB Output is correct
8 Correct 98 ms 26120 KB Output is correct
9 Correct 86 ms 25904 KB Output is correct
10 Correct 73 ms 26188 KB Output is correct
11 Correct 19 ms 21040 KB Output is correct
12 Correct 70 ms 25848 KB Output is correct
13 Runtime error 50 ms 33252 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -