oj.uz

답안 #660457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660457 2022-11-21T22:52:22 Z GusterGoose27 From Hacks to Snitches (BOI21_watchmen) C++11
0 / 100
 95 ms 30644 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) {}
	pii pair() {
		return pii(x, w);
	}
};

bool operator<(const edge &a, const edge &b) {
	return pii(a.x, a.w) < pii(b.x, b.w);
}

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));
	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);
}

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[cur] > 0 && (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 req_pos = ((mod[cur]+sz[cur]-2*p.w-1) % sz[cur]);
				int cur_pos = (dist[cur] % sz[cur]);
				ndist = dist[cur]+p.w + ((req_pos+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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21968 KB Output is correct
2 Incorrect 89 ms 30552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21960 KB Output is correct
2 Incorrect 95 ms 30644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21960 KB Output is correct
2 Incorrect 95 ms 30644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21960 KB Output is correct
2 Incorrect 95 ms 30644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21968 KB Output is correct
2 Incorrect 89 ms 30552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21968 KB Output is correct
2 Incorrect 89 ms 30552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 21968 KB Output is correct
2 Incorrect 89 ms 30552 KB Output isn't correct
3 Halted 0 ms 0 KB -