oj.uz

Submission #660466

# Submission time Handle Problem Language Result Execution time Memory
660466 2022-11-21T23:28:42 Z GusterGoose27 From Hacks to Snitches (BOI21_watchmen) C++11
15 / 100
 6000 ms 390484 KB 
#pragma GCC optimize("Ofast")

#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 || sz[i] == 0) return;
	edge l = *edges[i].begin();
	edge r = *edges[i].rbegin();
	if (l.dir) swap(l, r);
	edges[i].clear();
	edges[l.x].erase(edge(i, l.w, 1));
	edges[r.x].erase(edge(i, r.w));
	if (l.x != r.x) {
		edges[l.x].insert(edge(r.x, l.w+r.w, 1));
		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 98 ms 21960 KB Output is correct
2 Correct 93 ms 25504 KB Output is correct
3 Correct 96 ms 25460 KB Output is correct
4 Correct 106 ms 25604 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 99 ms 25452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 22068 KB Output is correct
2 Correct 99 ms 25500 KB Output is correct
3 Correct 106 ms 25476 KB Output is correct
4 Correct 108 ms 25660 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 100 ms 25560 KB Output is correct
7 Correct 100 ms 25552 KB Output is correct
8 Correct 108 ms 25548 KB Output is correct
9 Correct 91 ms 25420 KB Output is correct
10 Correct 101 ms 25688 KB Output is correct
11 Correct 114 ms 25484 KB Output is correct
12 Correct 98 ms 25468 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 22068 KB Output is correct
2 Correct 99 ms 25500 KB Output is correct
3 Correct 106 ms 25476 KB Output is correct
4 Correct 108 ms 25660 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 100 ms 25560 KB Output is correct
7 Correct 100 ms 25552 KB Output is correct
8 Correct 108 ms 25548 KB Output is correct
9 Correct 91 ms 25420 KB Output is correct
10 Correct 101 ms 25688 KB Output is correct
11 Correct 114 ms 25484 KB Output is correct
12 Correct 98 ms 25468 KB Output is correct
13 Correct 94 ms 21960 KB Output is correct
14 Correct 100 ms 25504 KB Output is correct
15 Correct 106 ms 25572 KB Output is correct
16 Correct 111 ms 25548 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 98 ms 25444 KB Output is correct
19 Correct 97 ms 25508 KB Output is correct
20 Correct 101 ms 25484 KB Output is correct
21 Correct 95 ms 25468 KB Output is correct
22 Correct 106 ms 25640 KB Output is correct
23 Correct 108 ms 25504 KB Output is correct
24 Correct 97 ms 25576 KB Output is correct
25 Execution timed out 6065 ms 390388 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 22068 KB Output is correct
2 Correct 99 ms 25500 KB Output is correct
3 Correct 106 ms 25476 KB Output is correct
4 Correct 108 ms 25660 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 100 ms 25560 KB Output is correct
7 Correct 100 ms 25552 KB Output is correct
8 Correct 108 ms 25548 KB Output is correct
9 Correct 91 ms 25420 KB Output is correct
10 Correct 101 ms 25688 KB Output is correct
11 Correct 114 ms 25484 KB Output is correct
12 Correct 98 ms 25468 KB Output is correct
13 Correct 94 ms 21960 KB Output is correct
14 Correct 100 ms 25504 KB Output is correct
15 Correct 106 ms 25572 KB Output is correct
16 Correct 111 ms 25548 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 98 ms 25444 KB Output is correct
19 Correct 97 ms 25508 KB Output is correct
20 Correct 101 ms 25484 KB Output is correct
21 Correct 95 ms 25468 KB Output is correct
22 Correct 106 ms 25640 KB Output is correct
23 Correct 108 ms 25504 KB Output is correct
24 Correct 97 ms 25576 KB Output is correct
25 Execution timed out 6065 ms 390388 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 21960 KB Output is correct
2 Correct 93 ms 25504 KB Output is correct
3 Correct 96 ms 25460 KB Output is correct
4 Correct 106 ms 25604 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 99 ms 25452 KB Output is correct
7 Correct 98 ms 22068 KB Output is correct
8 Correct 99 ms 25500 KB Output is correct
9 Correct 106 ms 25476 KB Output is correct
10 Correct 108 ms 25660 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 100 ms 25560 KB Output is correct
13 Correct 100 ms 25552 KB Output is correct
14 Correct 108 ms 25548 KB Output is correct
15 Correct 91 ms 25420 KB Output is correct
16 Correct 101 ms 25688 KB Output is correct
17 Correct 114 ms 25484 KB Output is correct
18 Correct 98 ms 25468 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 6 ms 12008 KB Output is correct
21 Correct 6 ms 12052 KB Output is correct
22 Correct 84 ms 22056 KB Output is correct
23 Correct 107 ms 25500 KB Output is correct
24 Correct 96 ms 25544 KB Output is correct
25 Correct 110 ms 25536 KB Output is correct
26 Correct 6 ms 11988 KB Output is correct
27 Correct 96 ms 25492 KB Output is correct
28 Correct 113 ms 25548 KB Output is correct
29 Correct 95 ms 25460 KB Output is correct
30 Correct 105 ms 25440 KB Output is correct
31 Correct 98 ms 25832 KB Output is correct
32 Correct 105 ms 25468 KB Output is correct
33 Correct 101 ms 25564 KB Output is correct
34 Execution timed out 6078 ms 390484 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 21960 KB Output is correct
2 Correct 93 ms 25504 KB Output is correct
3 Correct 96 ms 25460 KB Output is correct
4 Correct 106 ms 25604 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 99 ms 25452 KB Output is correct
7 Correct 98 ms 22068 KB Output is correct
8 Correct 99 ms 25500 KB Output is correct
9 Correct 106 ms 25476 KB Output is correct
10 Correct 108 ms 25660 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 100 ms 25560 KB Output is correct
13 Correct 100 ms 25552 KB Output is correct
14 Correct 108 ms 25548 KB Output is correct
15 Correct 91 ms 25420 KB Output is correct
16 Correct 101 ms 25688 KB Output is correct
17 Correct 114 ms 25484 KB Output is correct
18 Correct 98 ms 25468 KB Output is correct
19 Correct 94 ms 21960 KB Output is correct
20 Correct 100 ms 25504 KB Output is correct
21 Correct 106 ms 25572 KB Output is correct
22 Correct 111 ms 25548 KB Output is correct
23 Correct 6 ms 11988 KB Output is correct
24 Correct 98 ms 25444 KB Output is correct
25 Correct 97 ms 25508 KB Output is correct
26 Correct 101 ms 25484 KB Output is correct
27 Correct 95 ms 25468 KB Output is correct
28 Correct 106 ms 25640 KB Output is correct
29 Correct 108 ms 25504 KB Output is correct
30 Correct 97 ms 25576 KB Output is correct
31 Execution timed out 6065 ms 390388 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 21960 KB Output is correct
2 Correct 93 ms 25504 KB Output is correct
3 Correct 96 ms 25460 KB Output is correct
4 Correct 106 ms 25604 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 99 ms 25452 KB Output is correct
7 Correct 98 ms 22068 KB Output is correct
8 Correct 99 ms 25500 KB Output is correct
9 Correct 106 ms 25476 KB Output is correct
10 Correct 108 ms 25660 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 100 ms 25560 KB Output is correct
13 Correct 100 ms 25552 KB Output is correct
14 Correct 108 ms 25548 KB Output is correct
15 Correct 91 ms 25420 KB Output is correct
16 Correct 101 ms 25688 KB Output is correct
17 Correct 114 ms 25484 KB Output is correct
18 Correct 98 ms 25468 KB Output is correct
19 Correct 94 ms 21960 KB Output is correct
20 Correct 100 ms 25504 KB Output is correct
21 Correct 106 ms 25572 KB Output is correct
22 Correct 111 ms 25548 KB Output is correct
23 Correct 6 ms 11988 KB Output is correct
24 Correct 98 ms 25444 KB Output is correct
25 Correct 97 ms 25508 KB Output is correct
26 Correct 101 ms 25484 KB Output is correct
27 Correct 95 ms 25468 KB Output is correct
28 Correct 106 ms 25640 KB Output is correct
29 Correct 108 ms 25504 KB Output is correct
30 Correct 97 ms 25576 KB Output is correct
31 Execution timed out 6065 ms 390388 KB Time limit exceeded
32 Halted 0 ms 0 KB -