oj.uz

Submission #660467

# Submission time Handle Problem Language Result Execution time Memory
660467 2022-11-21T23:33:08 Z GusterGoose27 From Hacks to Snitches (BOI21_watchmen) C++11
15 / 100
 6000 ms 396344 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#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];
vector<edge> edge_vec[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 90 ms 27820 KB Output is correct
2 Correct 98 ms 31256 KB Output is correct
3 Correct 103 ms 31436 KB Output is correct
4 Correct 107 ms 31476 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 104 ms 31324 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 27976 KB Output is correct
2 Correct 100 ms 31372 KB Output is correct
3 Correct 101 ms 31392 KB Output is correct
4 Correct 109 ms 31400 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 100 ms 31360 KB Output is correct
7 Correct 99 ms 31424 KB Output is correct
8 Correct 98 ms 31308 KB Output is correct
9 Correct 99 ms 31524 KB Output is correct
10 Correct 105 ms 31556 KB Output is correct
11 Correct 105 ms 31340 KB Output is correct
12 Correct 106 ms 31412 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 27976 KB Output is correct
2 Correct 100 ms 31372 KB Output is correct
3 Correct 101 ms 31392 KB Output is correct
4 Correct 109 ms 31400 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 100 ms 31360 KB Output is correct
7 Correct 99 ms 31424 KB Output is correct
8 Correct 98 ms 31308 KB Output is correct
9 Correct 99 ms 31524 KB Output is correct
10 Correct 105 ms 31556 KB Output is correct
11 Correct 105 ms 31340 KB Output is correct
12 Correct 106 ms 31412 KB Output is correct
13 Correct 92 ms 27952 KB Output is correct
14 Correct 101 ms 31348 KB Output is correct
15 Correct 105 ms 31444 KB Output is correct
16 Correct 103 ms 31376 KB Output is correct
17 Correct 10 ms 17968 KB Output is correct
18 Correct 102 ms 31324 KB Output is correct
19 Correct 101 ms 31300 KB Output is correct
20 Correct 98 ms 31308 KB Output is correct
21 Correct 98 ms 31396 KB Output is correct
22 Correct 102 ms 31500 KB Output is correct
23 Correct 106 ms 31412 KB Output is correct
24 Correct 102 ms 31416 KB Output is correct
25 Execution timed out 6113 ms 396344 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 27976 KB Output is correct
2 Correct 100 ms 31372 KB Output is correct
3 Correct 101 ms 31392 KB Output is correct
4 Correct 109 ms 31400 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 100 ms 31360 KB Output is correct
7 Correct 99 ms 31424 KB Output is correct
8 Correct 98 ms 31308 KB Output is correct
9 Correct 99 ms 31524 KB Output is correct
10 Correct 105 ms 31556 KB Output is correct
11 Correct 105 ms 31340 KB Output is correct
12 Correct 106 ms 31412 KB Output is correct
13 Correct 92 ms 27952 KB Output is correct
14 Correct 101 ms 31348 KB Output is correct
15 Correct 105 ms 31444 KB Output is correct
16 Correct 103 ms 31376 KB Output is correct
17 Correct 10 ms 17968 KB Output is correct
18 Correct 102 ms 31324 KB Output is correct
19 Correct 101 ms 31300 KB Output is correct
20 Correct 98 ms 31308 KB Output is correct
21 Correct 98 ms 31396 KB Output is correct
22 Correct 102 ms 31500 KB Output is correct
23 Correct 106 ms 31412 KB Output is correct
24 Correct 102 ms 31416 KB Output is correct
25 Execution timed out 6113 ms 396344 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 27820 KB Output is correct
2 Correct 98 ms 31256 KB Output is correct
3 Correct 103 ms 31436 KB Output is correct
4 Correct 107 ms 31476 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 104 ms 31324 KB Output is correct
7 Correct 94 ms 27976 KB Output is correct
8 Correct 100 ms 31372 KB Output is correct
9 Correct 101 ms 31392 KB Output is correct
10 Correct 109 ms 31400 KB Output is correct
11 Correct 10 ms 17876 KB Output is correct
12 Correct 100 ms 31360 KB Output is correct
13 Correct 99 ms 31424 KB Output is correct
14 Correct 98 ms 31308 KB Output is correct
15 Correct 99 ms 31524 KB Output is correct
16 Correct 105 ms 31556 KB Output is correct
17 Correct 105 ms 31340 KB Output is correct
18 Correct 106 ms 31412 KB Output is correct
19 Correct 10 ms 17876 KB Output is correct
20 Correct 10 ms 17888 KB Output is correct
21 Correct 11 ms 17876 KB Output is correct
22 Correct 86 ms 27928 KB Output is correct
23 Correct 105 ms 31372 KB Output is correct
24 Correct 101 ms 31324 KB Output is correct
25 Correct 108 ms 31376 KB Output is correct
26 Correct 10 ms 17876 KB Output is correct
27 Correct 101 ms 31436 KB Output is correct
28 Correct 98 ms 31308 KB Output is correct
29 Correct 102 ms 31312 KB Output is correct
30 Correct 98 ms 31344 KB Output is correct
31 Correct 114 ms 31504 KB Output is correct
32 Correct 104 ms 31452 KB Output is correct
33 Correct 99 ms 31404 KB Output is correct
34 Execution timed out 6092 ms 396308 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 27820 KB Output is correct
2 Correct 98 ms 31256 KB Output is correct
3 Correct 103 ms 31436 KB Output is correct
4 Correct 107 ms 31476 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 104 ms 31324 KB Output is correct
7 Correct 94 ms 27976 KB Output is correct
8 Correct 100 ms 31372 KB Output is correct
9 Correct 101 ms 31392 KB Output is correct
10 Correct 109 ms 31400 KB Output is correct
11 Correct 10 ms 17876 KB Output is correct
12 Correct 100 ms 31360 KB Output is correct
13 Correct 99 ms 31424 KB Output is correct
14 Correct 98 ms 31308 KB Output is correct
15 Correct 99 ms 31524 KB Output is correct
16 Correct 105 ms 31556 KB Output is correct
17 Correct 105 ms 31340 KB Output is correct
18 Correct 106 ms 31412 KB Output is correct
19 Correct 92 ms 27952 KB Output is correct
20 Correct 101 ms 31348 KB Output is correct
21 Correct 105 ms 31444 KB Output is correct
22 Correct 103 ms 31376 KB Output is correct
23 Correct 10 ms 17968 KB Output is correct
24 Correct 102 ms 31324 KB Output is correct
25 Correct 101 ms 31300 KB Output is correct
26 Correct 98 ms 31308 KB Output is correct
27 Correct 98 ms 31396 KB Output is correct
28 Correct 102 ms 31500 KB Output is correct
29 Correct 106 ms 31412 KB Output is correct
30 Correct 102 ms 31416 KB Output is correct
31 Execution timed out 6113 ms 396344 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 27820 KB Output is correct
2 Correct 98 ms 31256 KB Output is correct
3 Correct 103 ms 31436 KB Output is correct
4 Correct 107 ms 31476 KB Output is correct
5 Correct 10 ms 17876 KB Output is correct
6 Correct 104 ms 31324 KB Output is correct
7 Correct 94 ms 27976 KB Output is correct
8 Correct 100 ms 31372 KB Output is correct
9 Correct 101 ms 31392 KB Output is correct
10 Correct 109 ms 31400 KB Output is correct
11 Correct 10 ms 17876 KB Output is correct
12 Correct 100 ms 31360 KB Output is correct
13 Correct 99 ms 31424 KB Output is correct
14 Correct 98 ms 31308 KB Output is correct
15 Correct 99 ms 31524 KB Output is correct
16 Correct 105 ms 31556 KB Output is correct
17 Correct 105 ms 31340 KB Output is correct
18 Correct 106 ms 31412 KB Output is correct
19 Correct 92 ms 27952 KB Output is correct
20 Correct 101 ms 31348 KB Output is correct
21 Correct 105 ms 31444 KB Output is correct
22 Correct 103 ms 31376 KB Output is correct
23 Correct 10 ms 17968 KB Output is correct
24 Correct 102 ms 31324 KB Output is correct
25 Correct 101 ms 31300 KB Output is correct
26 Correct 98 ms 31308 KB Output is correct
27 Correct 98 ms 31396 KB Output is correct
28 Correct 102 ms 31500 KB Output is correct
29 Correct 106 ms 31412 KB Output is correct
30 Correct 102 ms 31416 KB Output is correct
31 Execution timed out 6113 ms 396344 KB Time limit exceeded
32 Halted 0 ms 0 KB -