oj.uz

Submission #527860

# Submission time Handle Problem Language Result Execution time Memory
527860 2022-02-18T14:09:55 Z koioi.org-koosaga From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 164972 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
const int MAXN = 250005;

vector<lint> dist[MAXN];
vector<int> gph[MAXN];

struct node{
	int x, y; lint dist;
	bool operator<(const node &n)const{
		return dist > n.dist;
	}
};

void solve(int n, vector<pi> edg, vector<int> v, int s, int e){
	for(auto &[u, v] : edg){
		gph[u].push_back(v);
		gph[v].push_back(u);
	}
	int p = 0;
	vector<pi> cycs;
	for(int i = 0; i < sz(v); i++){
		for(int j = 0; j < v[i]; j++){
			dist[p].resize(v[i], 1e18);
			p++;
			cycs.emplace_back(i, j);
		}
	}
	while(p < n){
		dist[p++].resize(1, 1e18);
		cycs.emplace_back(-1, 0);
	}
	priority_queue<node> pq;
	auto enq = [&](int v, lint d){
		if(sz(dist[v]) > 1 && d % sz(dist[v]) == cycs[v].second) return;
		if(dist[v][d % sz(dist[v])] > d){
			dist[v][d % sz(dist[v])] = d;
			pq.push({v, (int)(d % sz(dist[v])), d});
		}
	};
	enq(s, 0);
	while(sz(pq)){
		auto x = pq.top(); pq.pop();
		if(dist[x.x][x.y] != x.dist) continue;
		enq(x.x, x.dist + 1);
		for(auto &y : gph[x.x]){
			if(cycs[x.x].first >= 0 && 
				cycs[x.x].first == cycs[y].first && 
				x.dist % sz(dist[x.x]) == cycs[y].second && 
				(x.dist + 1) % sz(dist[x.x]) == cycs[x.x].second){
				continue;
			}
			enq(y, x.dist + 1);
			if(cycs[x.x].first < 0 || cycs[x.x].first != cycs[y].first){
				if(sz(dist[y]) <= 1){
					for(int k = 0; k < sz(dist[y]); k++){
						enq(y, x.dist + 1 + sz(dist[x.x]) * k);
					}
				}
				else{
					enq(y, x.dist + 1);
					enq(y, x.dist + 1 + ((cycs[y].second - x.dist) % sz(dist[y]) + sz(dist[y])) % sz(dist[y]));
				}
			}
		}
	}
	lint ans = *min_element(all(dist[e]));
	if(ans < 1e17) cout << ans << "\n";
	else cout << "impossible\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m; cin >> n >> m;
	vector<pi> edg;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		edg.emplace_back(u-1, v-1);
	}
	vector<int> idx(n, -1);
	int cnt = 0;
	int k; cin >> k;
	vector<int> siz(k);
	for(int i = 0; i < k; i++){
		cin >> siz[i];
		for(int j = 0; j < siz[i]; j++){
			int v; cin >> v;
			idx[v - 1] = cnt++;
		}
	}
	for(int i = 0; i < n; i++){
		if(idx[i] == -1) idx[i] = cnt++;
	}
	for(auto &[u, v] : edg){
		u = idx[u];
		v = idx[v];
	}
	solve(n, edg, siz, idx[0], idx[n - 1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 15556 KB Output is correct
2 Correct 82 ms 23652 KB Output is correct
3 Correct 68 ms 22968 KB Output is correct
4 Correct 93 ms 23100 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 68 ms 22972 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15556 KB Output is correct
2 Correct 72 ms 23416 KB Output is correct
3 Correct 82 ms 22992 KB Output is correct
4 Correct 116 ms 23112 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 74 ms 23084 KB Output is correct
7 Correct 65 ms 22824 KB Output is correct
8 Correct 67 ms 22840 KB Output is correct
9 Correct 64 ms 22836 KB Output is correct
10 Correct 92 ms 23096 KB Output is correct
11 Correct 71 ms 22844 KB Output is correct
12 Correct 81 ms 23044 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15556 KB Output is correct
2 Correct 72 ms 23416 KB Output is correct
3 Correct 82 ms 22992 KB Output is correct
4 Correct 116 ms 23112 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 74 ms 23084 KB Output is correct
7 Correct 65 ms 22824 KB Output is correct
8 Correct 67 ms 22840 KB Output is correct
9 Correct 64 ms 22836 KB Output is correct
10 Correct 92 ms 23096 KB Output is correct
11 Correct 71 ms 22844 KB Output is correct
12 Correct 81 ms 23044 KB Output is correct
13 Correct 91 ms 15488 KB Output is correct
14 Correct 72 ms 23464 KB Output is correct
15 Correct 70 ms 22872 KB Output is correct
16 Correct 101 ms 23004 KB Output is correct
17 Correct 7 ms 12108 KB Output is correct
18 Correct 91 ms 22980 KB Output is correct
19 Correct 66 ms 22936 KB Output is correct
20 Correct 65 ms 22812 KB Output is correct
21 Correct 65 ms 22872 KB Output is correct
22 Correct 80 ms 23096 KB Output is correct
23 Correct 70 ms 22916 KB Output is correct
24 Correct 65 ms 22824 KB Output is correct
25 Correct 1322 ms 160136 KB Output is correct
26 Correct 1426 ms 164972 KB Output is correct
27 Correct 1130 ms 159404 KB Output is correct
28 Correct 1064 ms 163068 KB Output is correct
29 Execution timed out 6104 ms 156712 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 15556 KB Output is correct
2 Correct 72 ms 23416 KB Output is correct
3 Correct 82 ms 22992 KB Output is correct
4 Correct 116 ms 23112 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 74 ms 23084 KB Output is correct
7 Correct 65 ms 22824 KB Output is correct
8 Correct 67 ms 22840 KB Output is correct
9 Correct 64 ms 22836 KB Output is correct
10 Correct 92 ms 23096 KB Output is correct
11 Correct 71 ms 22844 KB Output is correct
12 Correct 81 ms 23044 KB Output is correct
13 Correct 91 ms 15488 KB Output is correct
14 Correct 72 ms 23464 KB Output is correct
15 Correct 70 ms 22872 KB Output is correct
16 Correct 101 ms 23004 KB Output is correct
17 Correct 7 ms 12108 KB Output is correct
18 Correct 91 ms 22980 KB Output is correct
19 Correct 66 ms 22936 KB Output is correct
20 Correct 65 ms 22812 KB Output is correct
21 Correct 65 ms 22872 KB Output is correct
22 Correct 80 ms 23096 KB Output is correct
23 Correct 70 ms 22916 KB Output is correct
24 Correct 65 ms 22824 KB Output is correct
25 Correct 1322 ms 160136 KB Output is correct
26 Correct 1426 ms 164972 KB Output is correct
27 Correct 1130 ms 159404 KB Output is correct
28 Correct 1064 ms 163068 KB Output is correct
29 Execution timed out 6104 ms 156712 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 15556 KB Output is correct
2 Correct 82 ms 23652 KB Output is correct
3 Correct 68 ms 22968 KB Output is correct
4 Correct 93 ms 23100 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 68 ms 22972 KB Output is correct
7 Correct 89 ms 15556 KB Output is correct
8 Correct 72 ms 23416 KB Output is correct
9 Correct 82 ms 22992 KB Output is correct
10 Correct 116 ms 23112 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 74 ms 23084 KB Output is correct
13 Correct 65 ms 22824 KB Output is correct
14 Correct 67 ms 22840 KB Output is correct
15 Correct 64 ms 22836 KB Output is correct
16 Correct 92 ms 23096 KB Output is correct
17 Correct 71 ms 22844 KB Output is correct
18 Correct 81 ms 23044 KB Output is correct
19 Correct 6 ms 11948 KB Output is correct
20 Correct 7 ms 11980 KB Output is correct
21 Incorrect 6 ms 11980 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 15556 KB Output is correct
2 Correct 82 ms 23652 KB Output is correct
3 Correct 68 ms 22968 KB Output is correct
4 Correct 93 ms 23100 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 68 ms 22972 KB Output is correct
7 Correct 89 ms 15556 KB Output is correct
8 Correct 72 ms 23416 KB Output is correct
9 Correct 82 ms 22992 KB Output is correct
10 Correct 116 ms 23112 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 74 ms 23084 KB Output is correct
13 Correct 65 ms 22824 KB Output is correct
14 Correct 67 ms 22840 KB Output is correct
15 Correct 64 ms 22836 KB Output is correct
16 Correct 92 ms 23096 KB Output is correct
17 Correct 71 ms 22844 KB Output is correct
18 Correct 81 ms 23044 KB Output is correct
19 Correct 91 ms 15488 KB Output is correct
20 Correct 72 ms 23464 KB Output is correct
21 Correct 70 ms 22872 KB Output is correct
22 Correct 101 ms 23004 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 91 ms 22980 KB Output is correct
25 Correct 66 ms 22936 KB Output is correct
26 Correct 65 ms 22812 KB Output is correct
27 Correct 65 ms 22872 KB Output is correct
28 Correct 80 ms 23096 KB Output is correct
29 Correct 70 ms 22916 KB Output is correct
30 Correct 65 ms 22824 KB Output is correct
31 Correct 1322 ms 160136 KB Output is correct
32 Correct 1426 ms 164972 KB Output is correct
33 Correct 1130 ms 159404 KB Output is correct
34 Correct 1064 ms 163068 KB Output is correct
35 Execution timed out 6104 ms 156712 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 15556 KB Output is correct
2 Correct 82 ms 23652 KB Output is correct
3 Correct 68 ms 22968 KB Output is correct
4 Correct 93 ms 23100 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 68 ms 22972 KB Output is correct
7 Correct 89 ms 15556 KB Output is correct
8 Correct 72 ms 23416 KB Output is correct
9 Correct 82 ms 22992 KB Output is correct
10 Correct 116 ms 23112 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 74 ms 23084 KB Output is correct
13 Correct 65 ms 22824 KB Output is correct
14 Correct 67 ms 22840 KB Output is correct
15 Correct 64 ms 22836 KB Output is correct
16 Correct 92 ms 23096 KB Output is correct
17 Correct 71 ms 22844 KB Output is correct
18 Correct 81 ms 23044 KB Output is correct
19 Correct 91 ms 15488 KB Output is correct
20 Correct 72 ms 23464 KB Output is correct
21 Correct 70 ms 22872 KB Output is correct
22 Correct 101 ms 23004 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 91 ms 22980 KB Output is correct
25 Correct 66 ms 22936 KB Output is correct
26 Correct 65 ms 22812 KB Output is correct
27 Correct 65 ms 22872 KB Output is correct
28 Correct 80 ms 23096 KB Output is correct
29 Correct 70 ms 22916 KB Output is correct
30 Correct 65 ms 22824 KB Output is correct
31 Correct 1322 ms 160136 KB Output is correct
32 Correct 1426 ms 164972 KB Output is correct
33 Correct 1130 ms 159404 KB Output is correct
34 Correct 1064 ms 163068 KB Output is correct
35 Execution timed out 6104 ms 156712 KB Time limit exceeded
36 Halted 0 ms 0 KB -