oj.uz

Submission #660465

# Submission time Handle Problem Language Result Execution time Memory
660465 2022-11-21T23:27:16 Z GusterGoose27 From Hacks to Snitches (BOI21_watchmen) C++11
15 / 100
 6000 ms 428892 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 || 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 101 ms 21948 KB Output is correct
2 Correct 100 ms 25444 KB Output is correct
3 Correct 110 ms 25588 KB Output is correct
4 Correct 102 ms 25592 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 103 ms 25552 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21972 KB Output is correct
2 Correct 97 ms 25420 KB Output is correct
3 Correct 103 ms 25572 KB Output is correct
4 Correct 107 ms 25604 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 107 ms 25472 KB Output is correct
7 Correct 110 ms 25552 KB Output is correct
8 Correct 105 ms 26700 KB Output is correct
9 Correct 101 ms 26572 KB Output is correct
10 Correct 106 ms 26744 KB Output is correct
11 Correct 103 ms 26652 KB Output is correct
12 Correct 103 ms 26824 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21972 KB Output is correct
2 Correct 97 ms 25420 KB Output is correct
3 Correct 103 ms 25572 KB Output is correct
4 Correct 107 ms 25604 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 107 ms 25472 KB Output is correct
7 Correct 110 ms 25552 KB Output is correct
8 Correct 105 ms 26700 KB Output is correct
9 Correct 101 ms 26572 KB Output is correct
10 Correct 106 ms 26744 KB Output is correct
11 Correct 103 ms 26652 KB Output is correct
12 Correct 103 ms 26824 KB Output is correct
13 Correct 94 ms 22652 KB Output is correct
14 Correct 95 ms 26604 KB Output is correct
15 Correct 114 ms 26724 KB Output is correct
16 Correct 111 ms 26656 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 116 ms 26640 KB Output is correct
19 Correct 100 ms 26668 KB Output is correct
20 Correct 99 ms 26716 KB Output is correct
21 Correct 97 ms 26696 KB Output is correct
22 Correct 103 ms 26772 KB Output is correct
23 Correct 103 ms 26688 KB Output is correct
24 Correct 101 ms 26720 KB Output is correct
25 Execution timed out 6089 ms 428892 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21972 KB Output is correct
2 Correct 97 ms 25420 KB Output is correct
3 Correct 103 ms 25572 KB Output is correct
4 Correct 107 ms 25604 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 107 ms 25472 KB Output is correct
7 Correct 110 ms 25552 KB Output is correct
8 Correct 105 ms 26700 KB Output is correct
9 Correct 101 ms 26572 KB Output is correct
10 Correct 106 ms 26744 KB Output is correct
11 Correct 103 ms 26652 KB Output is correct
12 Correct 103 ms 26824 KB Output is correct
13 Correct 94 ms 22652 KB Output is correct
14 Correct 95 ms 26604 KB Output is correct
15 Correct 114 ms 26724 KB Output is correct
16 Correct 111 ms 26656 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 116 ms 26640 KB Output is correct
19 Correct 100 ms 26668 KB Output is correct
20 Correct 99 ms 26716 KB Output is correct
21 Correct 97 ms 26696 KB Output is correct
22 Correct 103 ms 26772 KB Output is correct
23 Correct 103 ms 26688 KB Output is correct
24 Correct 101 ms 26720 KB Output is correct
25 Execution timed out 6089 ms 428892 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21948 KB Output is correct
2 Correct 100 ms 25444 KB Output is correct
3 Correct 110 ms 25588 KB Output is correct
4 Correct 102 ms 25592 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 103 ms 25552 KB Output is correct
7 Correct 93 ms 21972 KB Output is correct
8 Correct 97 ms 25420 KB Output is correct
9 Correct 103 ms 25572 KB Output is correct
10 Correct 107 ms 25604 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 107 ms 25472 KB Output is correct
13 Correct 110 ms 25552 KB Output is correct
14 Correct 105 ms 26700 KB Output is correct
15 Correct 101 ms 26572 KB Output is correct
16 Correct 106 ms 26744 KB Output is correct
17 Correct 103 ms 26652 KB Output is correct
18 Correct 103 ms 26824 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 6 ms 11988 KB Output is correct
21 Correct 8 ms 12076 KB Output is correct
22 Correct 95 ms 22620 KB Output is correct
23 Correct 97 ms 26648 KB Output is correct
24 Correct 100 ms 26608 KB Output is correct
25 Correct 103 ms 26744 KB Output is correct
26 Correct 6 ms 11984 KB Output is correct
27 Correct 100 ms 26660 KB Output is correct
28 Correct 105 ms 26756 KB Output is correct
29 Correct 97 ms 26620 KB Output is correct
30 Correct 98 ms 26572 KB Output is correct
31 Correct 104 ms 26828 KB Output is correct
32 Correct 114 ms 26736 KB Output is correct
33 Correct 99 ms 26640 KB Output is correct
34 Execution timed out 6046 ms 428864 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21948 KB Output is correct
2 Correct 100 ms 25444 KB Output is correct
3 Correct 110 ms 25588 KB Output is correct
4 Correct 102 ms 25592 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 103 ms 25552 KB Output is correct
7 Correct 93 ms 21972 KB Output is correct
8 Correct 97 ms 25420 KB Output is correct
9 Correct 103 ms 25572 KB Output is correct
10 Correct 107 ms 25604 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 107 ms 25472 KB Output is correct
13 Correct 110 ms 25552 KB Output is correct
14 Correct 105 ms 26700 KB Output is correct
15 Correct 101 ms 26572 KB Output is correct
16 Correct 106 ms 26744 KB Output is correct
17 Correct 103 ms 26652 KB Output is correct
18 Correct 103 ms 26824 KB Output is correct
19 Correct 94 ms 22652 KB Output is correct
20 Correct 95 ms 26604 KB Output is correct
21 Correct 114 ms 26724 KB Output is correct
22 Correct 111 ms 26656 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 116 ms 26640 KB Output is correct
25 Correct 100 ms 26668 KB Output is correct
26 Correct 99 ms 26716 KB Output is correct
27 Correct 97 ms 26696 KB Output is correct
28 Correct 103 ms 26772 KB Output is correct
29 Correct 103 ms 26688 KB Output is correct
30 Correct 101 ms 26720 KB Output is correct
31 Execution timed out 6089 ms 428892 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 21948 KB Output is correct
2 Correct 100 ms 25444 KB Output is correct
3 Correct 110 ms 25588 KB Output is correct
4 Correct 102 ms 25592 KB Output is correct
5 Correct 6 ms 12072 KB Output is correct
6 Correct 103 ms 25552 KB Output is correct
7 Correct 93 ms 21972 KB Output is correct
8 Correct 97 ms 25420 KB Output is correct
9 Correct 103 ms 25572 KB Output is correct
10 Correct 107 ms 25604 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 107 ms 25472 KB Output is correct
13 Correct 110 ms 25552 KB Output is correct
14 Correct 105 ms 26700 KB Output is correct
15 Correct 101 ms 26572 KB Output is correct
16 Correct 106 ms 26744 KB Output is correct
17 Correct 103 ms 26652 KB Output is correct
18 Correct 103 ms 26824 KB Output is correct
19 Correct 94 ms 22652 KB Output is correct
20 Correct 95 ms 26604 KB Output is correct
21 Correct 114 ms 26724 KB Output is correct
22 Correct 111 ms 26656 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 116 ms 26640 KB Output is correct
25 Correct 100 ms 26668 KB Output is correct
26 Correct 99 ms 26716 KB Output is correct
27 Correct 97 ms 26696 KB Output is correct
28 Correct 103 ms 26772 KB Output is correct
29 Correct 103 ms 26688 KB Output is correct
30 Correct 101 ms 26720 KB Output is correct
31 Execution timed out 6089 ms 428892 KB Time limit exceeded
32 Halted 0 ms 0 KB -