oj.uz

Submission #660461

# Submission time Handle Problem Language Result Execution time Memory
660461 2022-11-21T23:17:23 Z GusterGoose27 From Hacks to Snitches (BOI21_watchmen) C++11
5 / 100
 117 ms 32368 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

class edge {
public:
	int x, w;
	bool dir; // 1 if guards go in this direction
	edge(int x, int w, bool d = 0) : x(x), w(w), dir(d) {}
};

pair<pii, bool> get_pair(const edge e) {
	return pair<pii, bool>(pii(e.x, e.w), e.dir);
}

bool operator<(const edge &a, const edge &b) {
	return get_pair(a) < get_pair(b);
}

const int MAXN = 25e4;
const int inf = 1e9;
set<edge> edges[MAXN];
// int prv[MAXN];
// int nxt[MAXN];
int sz[MAXN];
int mod[MAXN];
int dist[MAXN];
int n, m, k;

void prune(int i) {
	if (i == n-1 || i == 0 || edges[i].size() != 2) return;
	edge l = *edges[i].begin();
	edge r = *edges[i].rbegin();
	if (sz[i] > 0) {
		if (l.dir) swap(l, r);
		// nxt[l.x] = r.x;
		// prv[r.x] = l.x;
	}
	edges[i].clear();
	edges[l.x].erase(edge(i, l.w, (sz[i] > 0)));
	edges[r.x].erase(edge(i, r.w));
	if (l.x != r.x) {
		edges[l.x].insert(edge(r.x, l.w+r.w, (sz[i] > 0)));
		edges[r.x].insert(edge(l.x, l.w+r.w));
	}
	prune(l.x);
	prune(r.x);
}

bool cont(int l, int r, int p, int M) {
	if (l > r) r += M;
	return ((l <= p && p <= r) || (p+M <= r));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		edges[x].insert(edge(y, 1));
		edges[y].insert(edge(x, 1));
	}
	cin >> k;
	for (int i = 0; i < k; i++) {
		int t; cin >> t;
		vector<int> v;
		for (int j = 0; j < t; j++) {
			int x; cin >> x; x--;
			v.push_back(x);
		}
		for (int j = 0; j < t; j++) {
			// nxt[v[j]] = v[(j+1)%t];
			// prv[v[j]] = v[(j+n-1)%t];
			edges[v[j]].erase(edge(v[(j+1)%t], 1));
			edges[v[j]].insert(edge(v[(j+1)%t], 1, 1));
			sz[v[j]] = v.size();
			mod[v[j]] = j;
		}
	}
	for (int i = 0; i < n; i++) {
		if (edges[i].size() == 2) prune(i);
	}
	fill(dist, dist+n, inf);
	dist[0] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push(pii(0, 0));
	while (!pq.empty()) {
		pii t = pq.top();
		pq.pop();
		int cur = t.second;
		if (dist[cur] < t.first) continue;
		for (edge p: edges[cur]) {
			int nxtval = p.x;
			int ndist;
			if (sz[cur] == 0) ndist = dist[cur]+p.w;
			else if (sz[nxtval] == 0 || p.dir) {
				ndist = dist[cur]+p.w+((dist[cur]%sz[cur])==mod[cur]);
			}
			else {
				if (2*p.w+1 >= sz[cur]) continue;
				int mx_pos = ((mod[cur]+sz[cur]-2*p.w-1) % sz[cur]);
				int cur_pos = (dist[cur] % sz[cur]);
				if (cont(mod[cur]+1, mx_pos, cur_pos, sz[cur])) ndist = dist[cur]+p.w;
				else ndist = dist[cur]+p.w + ((mod[cur]+1+sz[cur]-cur_pos)%sz[cur]);
			}
			if (ndist < dist[nxtval]) {
				dist[nxtval] = ndist;
				pq.push(pii(ndist, nxtval));
			}
/*
Case 1: This isn't on a cycle. ez
Case 2: this is on a cycle. add 1 if we arrived right as the watchmen arrived
Case 3: both of these are on the same cycle and the watchmen goes from nxt to cur.
*/
		}
	}
	if (dist[n-1] == inf) cout << "impossible\n";
	else cout << dist[n-1] << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 21992 KB Output is correct
2 Correct 97 ms 30644 KB Output is correct
3 Correct 117 ms 29268 KB Output is correct
4 Correct 111 ms 32368 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 115 ms 30448 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22068 KB Output is correct
2 Correct 91 ms 30648 KB Output is correct
3 Correct 111 ms 29392 KB Output is correct
4 Correct 111 ms 32300 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 113 ms 30356 KB Output is correct
7 Incorrect 93 ms 28192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22068 KB Output is correct
2 Correct 91 ms 30648 KB Output is correct
3 Correct 111 ms 29392 KB Output is correct
4 Correct 111 ms 32300 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 113 ms 30356 KB Output is correct
7 Incorrect 93 ms 28192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22068 KB Output is correct
2 Correct 91 ms 30648 KB Output is correct
3 Correct 111 ms 29392 KB Output is correct
4 Correct 111 ms 32300 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 113 ms 30356 KB Output is correct
7 Incorrect 93 ms 28192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 21992 KB Output is correct
2 Correct 97 ms 30644 KB Output is correct
3 Correct 117 ms 29268 KB Output is correct
4 Correct 111 ms 32368 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 115 ms 30448 KB Output is correct
7 Correct 95 ms 22068 KB Output is correct
8 Correct 91 ms 30648 KB Output is correct
9 Correct 111 ms 29392 KB Output is correct
10 Correct 111 ms 32300 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 113 ms 30356 KB Output is correct
13 Incorrect 93 ms 28192 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 21992 KB Output is correct
2 Correct 97 ms 30644 KB Output is correct
3 Correct 117 ms 29268 KB Output is correct
4 Correct 111 ms 32368 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 115 ms 30448 KB Output is correct
7 Correct 95 ms 22068 KB Output is correct
8 Correct 91 ms 30648 KB Output is correct
9 Correct 111 ms 29392 KB Output is correct
10 Correct 111 ms 32300 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 113 ms 30356 KB Output is correct
13 Incorrect 93 ms 28192 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 21992 KB Output is correct
2 Correct 97 ms 30644 KB Output is correct
3 Correct 117 ms 29268 KB Output is correct
4 Correct 111 ms 32368 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 115 ms 30448 KB Output is correct
7 Correct 95 ms 22068 KB Output is correct
8 Correct 91 ms 30648 KB Output is correct
9 Correct 111 ms 29392 KB Output is correct
10 Correct 111 ms 32300 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 113 ms 30356 KB Output is correct
13 Incorrect 93 ms 28192 KB Output isn't correct
14 Halted 0 ms 0 KB -