oj.uz

Submission #660464

# Submission time Handle Problem Language Result Execution time Memory
660464 2022-11-21T23:22:40 Z GusterGoose27 From Hacks to Snitches (BOI21_watchmen) C++11
5 / 100
 112 ms 31160 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) return (l <= p) || (p <= r);
	return (l <= p && p <= 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)%sz[cur], 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 86 ms 22028 KB Output is correct
2 Correct 88 ms 30592 KB Output is correct
3 Correct 101 ms 28108 KB Output is correct
4 Correct 112 ms 31140 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 106 ms 29224 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 22112 KB Output is correct
2 Correct 97 ms 30624 KB Output is correct
3 Correct 105 ms 28208 KB Output is correct
4 Correct 110 ms 31160 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 106 ms 29300 KB Output is correct
7 Incorrect 89 ms 26988 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 22112 KB Output is correct
2 Correct 97 ms 30624 KB Output is correct
3 Correct 105 ms 28208 KB Output is correct
4 Correct 110 ms 31160 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 106 ms 29300 KB Output is correct
7 Incorrect 89 ms 26988 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 22112 KB Output is correct
2 Correct 97 ms 30624 KB Output is correct
3 Correct 105 ms 28208 KB Output is correct
4 Correct 110 ms 31160 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 106 ms 29300 KB Output is correct
7 Incorrect 89 ms 26988 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 22028 KB Output is correct
2 Correct 88 ms 30592 KB Output is correct
3 Correct 101 ms 28108 KB Output is correct
4 Correct 112 ms 31140 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 106 ms 29224 KB Output is correct
7 Correct 87 ms 22112 KB Output is correct
8 Correct 97 ms 30624 KB Output is correct
9 Correct 105 ms 28208 KB Output is correct
10 Correct 110 ms 31160 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 106 ms 29300 KB Output is correct
13 Incorrect 89 ms 26988 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 22028 KB Output is correct
2 Correct 88 ms 30592 KB Output is correct
3 Correct 101 ms 28108 KB Output is correct
4 Correct 112 ms 31140 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 106 ms 29224 KB Output is correct
7 Correct 87 ms 22112 KB Output is correct
8 Correct 97 ms 30624 KB Output is correct
9 Correct 105 ms 28208 KB Output is correct
10 Correct 110 ms 31160 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 106 ms 29300 KB Output is correct
13 Incorrect 89 ms 26988 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 22028 KB Output is correct
2 Correct 88 ms 30592 KB Output is correct
3 Correct 101 ms 28108 KB Output is correct
4 Correct 112 ms 31140 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 106 ms 29224 KB Output is correct
7 Correct 87 ms 22112 KB Output is correct
8 Correct 97 ms 30624 KB Output is correct
9 Correct 105 ms 28208 KB Output is correct
10 Correct 110 ms 31160 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 106 ms 29300 KB Output is correct
13 Incorrect 89 ms 26988 KB Output isn't correct
14 Halted 0 ms 0 KB -