oj.uz

Submission #828889

# Submission time Handle Problem Language Result Execution time Memory
828889 2023-08-17T18:35:02 Z QwertyPi From Hacks to Snitches (BOI21_watchmen) C++14
25 / 100
 6000 ms 200464 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
 
using namespace std;
 
const int MAXN = 2.5e5 + 11;
const int MAXV = 2750 + 11;
const int MAXC = 1500 + 11;
const int MAXA = 2e6 + 11;
int cyc[MAXN], ci[MAXN], cl[MAXN], vi[MAXN];
vector<int> G[MAXN], H[MAXN];
int dp[MAXN], dp2[MAXV][MAXC];
bool vis[MAXN], vis2[MAXV][MAXC];
vector<pair<int, int>> ch[MAXA];
vector<int> cycles[MAXV];
 
struct edge{
	int u, v;
};
 
bool in_cycle(int v){
	return cyc[v] != 0;
}
 
int cycle_nxt(int v){
	assert(cyc[v] != 0);
	return cycles[cyc[v]][(ci[v] + 1) % cl[v]];
}
 
int cycle_prv(int v){
	assert(cyc[v] != 0);
	return cycles[cyc[v]][(ci[v] + cl[v] - 1) % cl[v]];
}
 
int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	vector<edge> E;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		E.push_back({u, v});
	}
	int s_cyc = 0;
	int k; cin >> k;
	for(int i = 0; i < k; i++){
		vector<int> v;
		int l; cin >> l;
		for(int j = 0; j < l; j++){
			int u; cin >> u; v.push_back(u);
		}
		cycles[i + 1] = v;
		for(int j = 0; j < l; j++) cyc[v[j]] = i + 1, ci[v[j]] = j, cl[v[j]] = v.size(), vi[v[j]] = 1 + s_cyc + j; s_cyc += l;
	}
 
	for(int i = 0; i < m; i++){
		edge e = E[i];
		if(!in_cycle(e.u)) swap(e.u, e.v);
		if(in_cycle(e.u) && in_cycle(e.v)){
			if(e.u == cycle_nxt(e.v) || e.u == cycle_prv(e.v))
				continue;
			H[e.u].push_back(e.v);
			H[e.v].push_back(e.u);
		}else{
			G[e.u].push_back(e.v);
			G[e.v].push_back(e.u);
		}
	}
	// for(int i = 1; i <= n; i++) cout << cyc[i] << ' '; cout << endl;
	// for(int i = 1; i <= n; i++) cout << ci[i] << ' '; cout << endl;
	// for(int i = 1; i <= n; i++) cout << vi[i] << ' '; cout << endl;
 
	memset(dp, 0x3f, sizeof(dp));
	memset(dp2, 0x3f, sizeof(dp2));
 
	dp[1] = 0; ch[0].push_back({1, 0});
	for(int d = 0; d < MAXA; d++){
		for(auto [v, i] : ch[d]){
			// printf("dist[(%d %d)] = %d\n", v, i, d);
			if(!in_cycle(v)){
				assert(i == 0);
				if(vis[v]) continue; vis[v] = true;
				for(auto u : G[v]){
					if(!in_cycle(u)){
						if(dp[v] + 1 < dp[u]){
							dp[u] = dp[v] + 1;
							ch[d + 1].push_back({u, 0});
						}
					}else{
						vector<int> J;
						J.push_back(0); J.push_back(1);
						J.push_back((((ci[u] - dp[v]) % cl[u]) + cl[u]) % cl[u]);
						for(int j : J){
							int dst = dp[v] + 1 + j;
							if(dst % cl[u] == ci[u]) continue;
							if(dst < dp2[vi[u]][dst % cl[u]]){
								dp2[vi[u]][dst % cl[u]] = dst;
								ch[dst].push_back({u, dst % cl[u]});
							}
						}
					}
				}
			}else{
				if(!vis[v]){
					for(int i = 0; i < cl[v]; i++){
						dp[v] = min(dp[v], dp2[vi[v]][i]);
					}
					// printf("dp[%d] = %d\n", v, dp[v]);
					vis[v] = true;
					for(auto u : G[v]){
						assert(!in_cycle(u));
						if(dp[v] + 1 < dp[u]){
							dp[u] = dp[v] + 1;
							ch[d + 1].push_back({u, 0});
						}
					}
				}
 
				assert(d % cl[v] != ci[v]);
 
				if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
				// stationery
				if((d + 1) % cl[v] != ci[v] && d + 1 < dp2[vi[v]][(d + 1) % cl[v]]){
					dp2[vi[v]][(d + 1) % cl[v]] = d + 1;
					ch[d + 1].push_back({v, (d + 1) % cl[v]});
				}
 
				for(auto u : H[v]){
					for(int j = 0; j <= (cl[u] + cl[v] - 1) / cl[v]; j++){
						int dst = d + 1 + j * cl[v];
						if(dst % cl[u] != ci[u] && dst < dp2[vi[u]][dst % cl[u]]){
							dp2[vi[u]][dst % cl[u]] = dst;
							ch[dst].push_back({u, dst % cl[u]});
						}
					}
				}
 
				// forward
				int u = cycle_nxt(v);
				if(d + 1 < dp2[vi[u]][(d + 1) % cl[u]]){
					dp2[vi[u]][(d + 1) % cl[u]] = d + 1;
					ch[d + 1].push_back({u, (d + 1) % cl[u]});
				}
				
				// backward
				u = cycle_prv(v);
				if((d + 1) % cl[v] != ci[v] && (d + 2) % cl[v] != ci[v] && d + 1 < dp2[vi[u]][(d + 1) % cl[u]]){
					dp2[vi[u]][(d + 1) % cl[u]] = d + 1;
					ch[d + 1].push_back({u, (d + 1) % cl[u]});
				}
			}
		}
		ch[d].clear();
	}
	if(dp[n] == 0x3f3f3f3f){
		cout << "impossible" << endl;
	}else{
		cout << dp[n] << endl;
	}
}

Compilation message

watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:53:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   53 |   for(int j = 0; j < l; j++) cyc[v[j]] = i + 1, ci[v[j]] = j, cl[v[j]] = v.size(), vi[v[j]] = 1 + s_cyc + j; s_cyc += l;
      |   ^~~
watchmen.cpp:53:110: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |   for(int j = 0; j < l; j++) cyc[v[j]] = i + 1, ci[v[j]] = j, cl[v[j]] = v.size(), vi[v[j]] = 1 + s_cyc + j; s_cyc += l;
      |                                                                                                              ^~~~~
watchmen.cpp:78:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |   for(auto [v, i] : ch[d]){
      |            ^
watchmen.cpp:82:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |     if(vis[v]) continue; vis[v] = true;
      |     ^~
watchmen.cpp:82:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |     if(vis[v]) continue; vis[v] = true;
      |                          ^~~
watchmen.cpp:121:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  121 |     if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
      |     ^~
watchmen.cpp:121:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  121 |     if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
      |                                          ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 78860 KB Output is correct
2 Correct 77 ms 85912 KB Output is correct
3 Correct 72 ms 84604 KB Output is correct
4 Correct 124 ms 84160 KB Output is correct
5 Correct 38 ms 76772 KB Output is correct
6 Correct 74 ms 84364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 78856 KB Output is correct
2 Correct 77 ms 85944 KB Output is correct
3 Correct 73 ms 84596 KB Output is correct
4 Correct 120 ms 84224 KB Output is correct
5 Correct 45 ms 76756 KB Output is correct
6 Correct 84 ms 84400 KB Output is correct
7 Correct 88 ms 84700 KB Output is correct
8 Correct 75 ms 84764 KB Output is correct
9 Correct 72 ms 84856 KB Output is correct
10 Correct 81 ms 83748 KB Output is correct
11 Correct 71 ms 83116 KB Output is correct
12 Correct 74 ms 84300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 78856 KB Output is correct
2 Correct 77 ms 85944 KB Output is correct
3 Correct 73 ms 84596 KB Output is correct
4 Correct 120 ms 84224 KB Output is correct
5 Correct 45 ms 76756 KB Output is correct
6 Correct 84 ms 84400 KB Output is correct
7 Correct 88 ms 84700 KB Output is correct
8 Correct 75 ms 84764 KB Output is correct
9 Correct 72 ms 84856 KB Output is correct
10 Correct 81 ms 83748 KB Output is correct
11 Correct 71 ms 83116 KB Output is correct
12 Correct 74 ms 84300 KB Output is correct
13 Correct 99 ms 78876 KB Output is correct
14 Correct 79 ms 85744 KB Output is correct
15 Correct 75 ms 84548 KB Output is correct
16 Correct 119 ms 84208 KB Output is correct
17 Correct 39 ms 76772 KB Output is correct
18 Correct 72 ms 84296 KB Output is correct
19 Correct 74 ms 84680 KB Output is correct
20 Correct 81 ms 84712 KB Output is correct
21 Correct 79 ms 84876 KB Output is correct
22 Correct 80 ms 83748 KB Output is correct
23 Correct 71 ms 83136 KB Output is correct
24 Correct 72 ms 84240 KB Output is correct
25 Correct 746 ms 148388 KB Output is correct
26 Correct 787 ms 154328 KB Output is correct
27 Correct 703 ms 150468 KB Output is correct
28 Correct 690 ms 154860 KB Output is correct
29 Correct 1106 ms 141704 KB Output is correct
30 Correct 1165 ms 144632 KB Output is correct
31 Correct 832 ms 154316 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 78856 KB Output is correct
2 Correct 77 ms 85944 KB Output is correct
3 Correct 73 ms 84596 KB Output is correct
4 Correct 120 ms 84224 KB Output is correct
5 Correct 45 ms 76756 KB Output is correct
6 Correct 84 ms 84400 KB Output is correct
7 Correct 88 ms 84700 KB Output is correct
8 Correct 75 ms 84764 KB Output is correct
9 Correct 72 ms 84856 KB Output is correct
10 Correct 81 ms 83748 KB Output is correct
11 Correct 71 ms 83116 KB Output is correct
12 Correct 74 ms 84300 KB Output is correct
13 Correct 99 ms 78876 KB Output is correct
14 Correct 79 ms 85744 KB Output is correct
15 Correct 75 ms 84548 KB Output is correct
16 Correct 119 ms 84208 KB Output is correct
17 Correct 39 ms 76772 KB Output is correct
18 Correct 72 ms 84296 KB Output is correct
19 Correct 74 ms 84680 KB Output is correct
20 Correct 81 ms 84712 KB Output is correct
21 Correct 79 ms 84876 KB Output is correct
22 Correct 80 ms 83748 KB Output is correct
23 Correct 71 ms 83136 KB Output is correct
24 Correct 72 ms 84240 KB Output is correct
25 Correct 746 ms 148388 KB Output is correct
26 Correct 787 ms 154328 KB Output is correct
27 Correct 703 ms 150468 KB Output is correct
28 Correct 690 ms 154860 KB Output is correct
29 Correct 1106 ms 141704 KB Output is correct
30 Correct 1165 ms 144632 KB Output is correct
31 Correct 832 ms 154316 KB Output is correct
32 Correct 92 ms 78752 KB Output is correct
33 Correct 78 ms 86060 KB Output is correct
34 Correct 73 ms 84936 KB Output is correct
35 Correct 115 ms 84516 KB Output is correct
36 Correct 39 ms 76756 KB Output is correct
37 Correct 73 ms 84752 KB Output is correct
38 Correct 82 ms 85052 KB Output is correct
39 Correct 73 ms 85068 KB Output is correct
40 Correct 75 ms 85340 KB Output is correct
41 Correct 81 ms 84112 KB Output is correct
42 Correct 79 ms 83596 KB Output is correct
43 Correct 76 ms 84716 KB Output is correct
44 Correct 779 ms 148364 KB Output is correct
45 Correct 746 ms 154424 KB Output is correct
46 Correct 715 ms 150516 KB Output is correct
47 Correct 664 ms 154840 KB Output is correct
48 Correct 1091 ms 141904 KB Output is correct
49 Correct 1207 ms 144652 KB Output is correct
50 Correct 817 ms 154336 KB Output is correct
51 Correct 946 ms 175860 KB Output is correct
52 Correct 1085 ms 200464 KB Output is correct
53 Correct 897 ms 178556 KB Output is correct
54 Correct 686 ms 152948 KB Output is correct
55 Execution timed out 6084 ms 152592 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 78860 KB Output is correct
2 Correct 77 ms 85912 KB Output is correct
3 Correct 72 ms 84604 KB Output is correct
4 Correct 124 ms 84160 KB Output is correct
5 Correct 38 ms 76772 KB Output is correct
6 Correct 74 ms 84364 KB Output is correct
7 Correct 98 ms 78856 KB Output is correct
8 Correct 77 ms 85944 KB Output is correct
9 Correct 73 ms 84596 KB Output is correct
10 Correct 120 ms 84224 KB Output is correct
11 Correct 45 ms 76756 KB Output is correct
12 Correct 84 ms 84400 KB Output is correct
13 Correct 88 ms 84700 KB Output is correct
14 Correct 75 ms 84764 KB Output is correct
15 Correct 72 ms 84856 KB Output is correct
16 Correct 81 ms 83748 KB Output is correct
17 Correct 71 ms 83116 KB Output is correct
18 Correct 74 ms 84300 KB Output is correct
19 Correct 40 ms 76412 KB Output is correct
20 Correct 39 ms 76384 KB Output is correct
21 Correct 40 ms 76392 KB Output is correct
22 Correct 94 ms 78856 KB Output is correct
23 Correct 82 ms 85760 KB Output is correct
24 Correct 75 ms 84628 KB Output is correct
25 Correct 115 ms 84108 KB Output is correct
26 Correct 47 ms 76756 KB Output is correct
27 Correct 79 ms 84376 KB Output is correct
28 Correct 89 ms 84676 KB Output is correct
29 Correct 77 ms 84760 KB Output is correct
30 Correct 77 ms 84912 KB Output is correct
31 Correct 83 ms 83656 KB Output is correct
32 Correct 75 ms 83096 KB Output is correct
33 Correct 76 ms 84276 KB Output is correct
34 Correct 785 ms 147492 KB Output is correct
35 Correct 803 ms 143440 KB Output is correct
36 Correct 785 ms 143464 KB Output is correct
37 Correct 744 ms 150232 KB Output is correct
38 Correct 764 ms 147588 KB Output is correct
39 Correct 948 ms 141180 KB Output is correct
40 Correct 979 ms 141904 KB Output is correct
41 Correct 936 ms 141544 KB Output is correct
42 Correct 783 ms 147404 KB Output is correct
43 Correct 785 ms 151912 KB Output is correct
44 Correct 781 ms 152024 KB Output is correct
45 Incorrect 730 ms 143616 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 78860 KB Output is correct
2 Correct 77 ms 85912 KB Output is correct
3 Correct 72 ms 84604 KB Output is correct
4 Correct 124 ms 84160 KB Output is correct
5 Correct 38 ms 76772 KB Output is correct
6 Correct 74 ms 84364 KB Output is correct
7 Correct 98 ms 78856 KB Output is correct
8 Correct 77 ms 85944 KB Output is correct
9 Correct 73 ms 84596 KB Output is correct
10 Correct 120 ms 84224 KB Output is correct
11 Correct 45 ms 76756 KB Output is correct
12 Correct 84 ms 84400 KB Output is correct
13 Correct 88 ms 84700 KB Output is correct
14 Correct 75 ms 84764 KB Output is correct
15 Correct 72 ms 84856 KB Output is correct
16 Correct 81 ms 83748 KB Output is correct
17 Correct 71 ms 83116 KB Output is correct
18 Correct 74 ms 84300 KB Output is correct
19 Correct 99 ms 78876 KB Output is correct
20 Correct 79 ms 85744 KB Output is correct
21 Correct 75 ms 84548 KB Output is correct
22 Correct 119 ms 84208 KB Output is correct
23 Correct 39 ms 76772 KB Output is correct
24 Correct 72 ms 84296 KB Output is correct
25 Correct 74 ms 84680 KB Output is correct
26 Correct 81 ms 84712 KB Output is correct
27 Correct 79 ms 84876 KB Output is correct
28 Correct 80 ms 83748 KB Output is correct
29 Correct 71 ms 83136 KB Output is correct
30 Correct 72 ms 84240 KB Output is correct
31 Correct 746 ms 148388 KB Output is correct
32 Correct 787 ms 154328 KB Output is correct
33 Correct 703 ms 150468 KB Output is correct
34 Correct 690 ms 154860 KB Output is correct
35 Correct 1106 ms 141704 KB Output is correct
36 Correct 1165 ms 144632 KB Output is correct
37 Correct 832 ms 154316 KB Output is correct
38 Correct 40 ms 76412 KB Output is correct
39 Correct 39 ms 76384 KB Output is correct
40 Correct 40 ms 76392 KB Output is correct
41 Correct 94 ms 78856 KB Output is correct
42 Correct 82 ms 85760 KB Output is correct
43 Correct 75 ms 84628 KB Output is correct
44 Correct 115 ms 84108 KB Output is correct
45 Correct 47 ms 76756 KB Output is correct
46 Correct 79 ms 84376 KB Output is correct
47 Correct 89 ms 84676 KB Output is correct
48 Correct 77 ms 84760 KB Output is correct
49 Correct 77 ms 84912 KB Output is correct
50 Correct 83 ms 83656 KB Output is correct
51 Correct 75 ms 83096 KB Output is correct
52 Correct 76 ms 84276 KB Output is correct
53 Correct 785 ms 147492 KB Output is correct
54 Correct 803 ms 143440 KB Output is correct
55 Correct 785 ms 143464 KB Output is correct
56 Correct 744 ms 150232 KB Output is correct
57 Correct 764 ms 147588 KB Output is correct
58 Correct 948 ms 141180 KB Output is correct
59 Correct 979 ms 141904 KB Output is correct
60 Correct 936 ms 141544 KB Output is correct
61 Correct 783 ms 147404 KB Output is correct
62 Correct 785 ms 151912 KB Output is correct
63 Correct 781 ms 152024 KB Output is correct
64 Incorrect 730 ms 143616 KB Output isn't correct
65 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 78860 KB Output is correct
2 Correct 77 ms 85912 KB Output is correct
3 Correct 72 ms 84604 KB Output is correct
4 Correct 124 ms 84160 KB Output is correct
5 Correct 38 ms 76772 KB Output is correct
6 Correct 74 ms 84364 KB Output is correct
7 Correct 98 ms 78856 KB Output is correct
8 Correct 77 ms 85944 KB Output is correct
9 Correct 73 ms 84596 KB Output is correct
10 Correct 120 ms 84224 KB Output is correct
11 Correct 45 ms 76756 KB Output is correct
12 Correct 84 ms 84400 KB Output is correct
13 Correct 88 ms 84700 KB Output is correct
14 Correct 75 ms 84764 KB Output is correct
15 Correct 72 ms 84856 KB Output is correct
16 Correct 81 ms 83748 KB Output is correct
17 Correct 71 ms 83116 KB Output is correct
18 Correct 74 ms 84300 KB Output is correct
19 Correct 99 ms 78876 KB Output is correct
20 Correct 79 ms 85744 KB Output is correct
21 Correct 75 ms 84548 KB Output is correct
22 Correct 119 ms 84208 KB Output is correct
23 Correct 39 ms 76772 KB Output is correct
24 Correct 72 ms 84296 KB Output is correct
25 Correct 74 ms 84680 KB Output is correct
26 Correct 81 ms 84712 KB Output is correct
27 Correct 79 ms 84876 KB Output is correct
28 Correct 80 ms 83748 KB Output is correct
29 Correct 71 ms 83136 KB Output is correct
30 Correct 72 ms 84240 KB Output is correct
31 Correct 746 ms 148388 KB Output is correct
32 Correct 787 ms 154328 KB Output is correct
33 Correct 703 ms 150468 KB Output is correct
34 Correct 690 ms 154860 KB Output is correct
35 Correct 1106 ms 141704 KB Output is correct
36 Correct 1165 ms 144632 KB Output is correct
37 Correct 832 ms 154316 KB Output is correct
38 Correct 92 ms 78752 KB Output is correct
39 Correct 78 ms 86060 KB Output is correct
40 Correct 73 ms 84936 KB Output is correct
41 Correct 115 ms 84516 KB Output is correct
42 Correct 39 ms 76756 KB Output is correct
43 Correct 73 ms 84752 KB Output is correct
44 Correct 82 ms 85052 KB Output is correct
45 Correct 73 ms 85068 KB Output is correct
46 Correct 75 ms 85340 KB Output is correct
47 Correct 81 ms 84112 KB Output is correct
48 Correct 79 ms 83596 KB Output is correct
49 Correct 76 ms 84716 KB Output is correct
50 Correct 779 ms 148364 KB Output is correct
51 Correct 746 ms 154424 KB Output is correct
52 Correct 715 ms 150516 KB Output is correct
53 Correct 664 ms 154840 KB Output is correct
54 Correct 1091 ms 141904 KB Output is correct
55 Correct 1207 ms 144652 KB Output is correct
56 Correct 817 ms 154336 KB Output is correct
57 Correct 946 ms 175860 KB Output is correct
58 Correct 1085 ms 200464 KB Output is correct
59 Correct 897 ms 178556 KB Output is correct
60 Correct 686 ms 152948 KB Output is correct
61 Execution timed out 6084 ms 152592 KB Time limit exceeded
62 Halted 0 ms 0 KB -