oj.uz

Submission #828868

# Submission time Handle Problem Language Result Execution time Memory
828868 2023-08-17T17:59:13 Z QwertyPi From Hacks to Snitches (BOI21_watchmen) C++14
40 / 100
 6000 ms 154920 KB 
#include <bits/stdc++.h>

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]; 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:51:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |   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:51:110: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |   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:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |   for(auto [v, i] : ch[d]){
      |            ^
watchmen.cpp:80:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   80 |     if(vis[v]) continue; vis[v] = true;
      |     ^~
watchmen.cpp:80:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   80 |     if(vis[v]) continue; vis[v] = true;
      |                          ^~~
watchmen.cpp:119:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  119 |     if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
      |     ^~
watchmen.cpp:119:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  119 |     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 1254 ms 78268 KB Output is correct
2 Correct 76 ms 84948 KB Output is correct
3 Correct 73 ms 83808 KB Output is correct
4 Correct 1284 ms 83400 KB Output is correct
5 Correct 40 ms 76620 KB Output is correct
6 Correct 77 ms 83640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 78268 KB Output is correct
2 Correct 96 ms 84936 KB Output is correct
3 Correct 76 ms 83824 KB Output is correct
4 Correct 1301 ms 83460 KB Output is correct
5 Correct 42 ms 76720 KB Output is correct
6 Correct 74 ms 83568 KB Output is correct
7 Correct 74 ms 83904 KB Output is correct
8 Correct 74 ms 83940 KB Output is correct
9 Correct 75 ms 84168 KB Output is correct
10 Correct 193 ms 82968 KB Output is correct
11 Correct 79 ms 82376 KB Output is correct
12 Correct 74 ms 83528 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 78268 KB Output is correct
2 Correct 96 ms 84936 KB Output is correct
3 Correct 76 ms 83824 KB Output is correct
4 Correct 1301 ms 83460 KB Output is correct
5 Correct 42 ms 76720 KB Output is correct
6 Correct 74 ms 83568 KB Output is correct
7 Correct 74 ms 83904 KB Output is correct
8 Correct 74 ms 83940 KB Output is correct
9 Correct 75 ms 84168 KB Output is correct
10 Correct 193 ms 82968 KB Output is correct
11 Correct 79 ms 82376 KB Output is correct
12 Correct 74 ms 83528 KB Output is correct
13 Correct 1258 ms 78268 KB Output is correct
14 Correct 77 ms 84944 KB Output is correct
15 Correct 77 ms 83784 KB Output is correct
16 Correct 1285 ms 83404 KB Output is correct
17 Correct 42 ms 76692 KB Output is correct
18 Correct 75 ms 83580 KB Output is correct
19 Correct 77 ms 83884 KB Output is correct
20 Correct 77 ms 83904 KB Output is correct
21 Correct 74 ms 84152 KB Output is correct
22 Correct 197 ms 82896 KB Output is correct
23 Correct 76 ms 82344 KB Output is correct
24 Correct 74 ms 83524 KB Output is correct
25 Correct 748 ms 148264 KB Output is correct
26 Correct 755 ms 154280 KB Output is correct
27 Correct 830 ms 150456 KB Output is correct
28 Correct 676 ms 154920 KB Output is correct
29 Execution timed out 6066 ms 140384 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 78268 KB Output is correct
2 Correct 96 ms 84936 KB Output is correct
3 Correct 76 ms 83824 KB Output is correct
4 Correct 1301 ms 83460 KB Output is correct
5 Correct 42 ms 76720 KB Output is correct
6 Correct 74 ms 83568 KB Output is correct
7 Correct 74 ms 83904 KB Output is correct
8 Correct 74 ms 83940 KB Output is correct
9 Correct 75 ms 84168 KB Output is correct
10 Correct 193 ms 82968 KB Output is correct
11 Correct 79 ms 82376 KB Output is correct
12 Correct 74 ms 83528 KB Output is correct
13 Correct 1258 ms 78268 KB Output is correct
14 Correct 77 ms 84944 KB Output is correct
15 Correct 77 ms 83784 KB Output is correct
16 Correct 1285 ms 83404 KB Output is correct
17 Correct 42 ms 76692 KB Output is correct
18 Correct 75 ms 83580 KB Output is correct
19 Correct 77 ms 83884 KB Output is correct
20 Correct 77 ms 83904 KB Output is correct
21 Correct 74 ms 84152 KB Output is correct
22 Correct 197 ms 82896 KB Output is correct
23 Correct 76 ms 82344 KB Output is correct
24 Correct 74 ms 83524 KB Output is correct
25 Correct 748 ms 148264 KB Output is correct
26 Correct 755 ms 154280 KB Output is correct
27 Correct 830 ms 150456 KB Output is correct
28 Correct 676 ms 154920 KB Output is correct
29 Execution timed out 6066 ms 140384 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 78268 KB Output is correct
2 Correct 76 ms 84948 KB Output is correct
3 Correct 73 ms 83808 KB Output is correct
4 Correct 1284 ms 83400 KB Output is correct
5 Correct 40 ms 76620 KB Output is correct
6 Correct 77 ms 83640 KB Output is correct
7 Correct 1259 ms 78268 KB Output is correct
8 Correct 96 ms 84936 KB Output is correct
9 Correct 76 ms 83824 KB Output is correct
10 Correct 1301 ms 83460 KB Output is correct
11 Correct 42 ms 76720 KB Output is correct
12 Correct 74 ms 83568 KB Output is correct
13 Correct 74 ms 83904 KB Output is correct
14 Correct 74 ms 83940 KB Output is correct
15 Correct 75 ms 84168 KB Output is correct
16 Correct 193 ms 82968 KB Output is correct
17 Correct 79 ms 82376 KB Output is correct
18 Correct 74 ms 83528 KB Output is correct
19 Correct 39 ms 76372 KB Output is correct
20 Correct 40 ms 76420 KB Output is correct
21 Correct 40 ms 76380 KB Output is correct
22 Correct 1257 ms 78276 KB Output is correct
23 Correct 77 ms 84904 KB Output is correct
24 Correct 75 ms 83748 KB Output is correct
25 Correct 1287 ms 83456 KB Output is correct
26 Correct 42 ms 76756 KB Output is correct
27 Correct 76 ms 83604 KB Output is correct
28 Correct 76 ms 83840 KB Output is correct
29 Correct 75 ms 84008 KB Output is correct
30 Correct 75 ms 84168 KB Output is correct
31 Correct 199 ms 82956 KB Output is correct
32 Correct 83 ms 82468 KB Output is correct
33 Correct 90 ms 83500 KB Output is correct
34 Correct 784 ms 147508 KB Output is correct
35 Correct 816 ms 143332 KB Output is correct
36 Correct 854 ms 143292 KB Output is correct
37 Correct 765 ms 150160 KB Output is correct
38 Correct 761 ms 147400 KB Output is correct
39 Correct 1666 ms 141152 KB Output is correct
40 Correct 1213 ms 142412 KB Output is correct
41 Correct 940 ms 141476 KB Output is correct
42 Correct 749 ms 147384 KB Output is correct
43 Correct 760 ms 151880 KB Output is correct
44 Correct 818 ms 152004 KB Output is correct
45 Correct 854 ms 145224 KB Output is correct
46 Correct 780 ms 147296 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 78268 KB Output is correct
2 Correct 76 ms 84948 KB Output is correct
3 Correct 73 ms 83808 KB Output is correct
4 Correct 1284 ms 83400 KB Output is correct
5 Correct 40 ms 76620 KB Output is correct
6 Correct 77 ms 83640 KB Output is correct
7 Correct 1259 ms 78268 KB Output is correct
8 Correct 96 ms 84936 KB Output is correct
9 Correct 76 ms 83824 KB Output is correct
10 Correct 1301 ms 83460 KB Output is correct
11 Correct 42 ms 76720 KB Output is correct
12 Correct 74 ms 83568 KB Output is correct
13 Correct 74 ms 83904 KB Output is correct
14 Correct 74 ms 83940 KB Output is correct
15 Correct 75 ms 84168 KB Output is correct
16 Correct 193 ms 82968 KB Output is correct
17 Correct 79 ms 82376 KB Output is correct
18 Correct 74 ms 83528 KB Output is correct
19 Correct 1258 ms 78268 KB Output is correct
20 Correct 77 ms 84944 KB Output is correct
21 Correct 77 ms 83784 KB Output is correct
22 Correct 1285 ms 83404 KB Output is correct
23 Correct 42 ms 76692 KB Output is correct
24 Correct 75 ms 83580 KB Output is correct
25 Correct 77 ms 83884 KB Output is correct
26 Correct 77 ms 83904 KB Output is correct
27 Correct 74 ms 84152 KB Output is correct
28 Correct 197 ms 82896 KB Output is correct
29 Correct 76 ms 82344 KB Output is correct
30 Correct 74 ms 83524 KB Output is correct
31 Correct 748 ms 148264 KB Output is correct
32 Correct 755 ms 154280 KB Output is correct
33 Correct 830 ms 150456 KB Output is correct
34 Correct 676 ms 154920 KB Output is correct
35 Execution timed out 6066 ms 140384 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 78268 KB Output is correct
2 Correct 76 ms 84948 KB Output is correct
3 Correct 73 ms 83808 KB Output is correct
4 Correct 1284 ms 83400 KB Output is correct
5 Correct 40 ms 76620 KB Output is correct
6 Correct 77 ms 83640 KB Output is correct
7 Correct 1259 ms 78268 KB Output is correct
8 Correct 96 ms 84936 KB Output is correct
9 Correct 76 ms 83824 KB Output is correct
10 Correct 1301 ms 83460 KB Output is correct
11 Correct 42 ms 76720 KB Output is correct
12 Correct 74 ms 83568 KB Output is correct
13 Correct 74 ms 83904 KB Output is correct
14 Correct 74 ms 83940 KB Output is correct
15 Correct 75 ms 84168 KB Output is correct
16 Correct 193 ms 82968 KB Output is correct
17 Correct 79 ms 82376 KB Output is correct
18 Correct 74 ms 83528 KB Output is correct
19 Correct 1258 ms 78268 KB Output is correct
20 Correct 77 ms 84944 KB Output is correct
21 Correct 77 ms 83784 KB Output is correct
22 Correct 1285 ms 83404 KB Output is correct
23 Correct 42 ms 76692 KB Output is correct
24 Correct 75 ms 83580 KB Output is correct
25 Correct 77 ms 83884 KB Output is correct
26 Correct 77 ms 83904 KB Output is correct
27 Correct 74 ms 84152 KB Output is correct
28 Correct 197 ms 82896 KB Output is correct
29 Correct 76 ms 82344 KB Output is correct
30 Correct 74 ms 83524 KB Output is correct
31 Correct 748 ms 148264 KB Output is correct
32 Correct 755 ms 154280 KB Output is correct
33 Correct 830 ms 150456 KB Output is correct
34 Correct 676 ms 154920 KB Output is correct
35 Execution timed out 6066 ms 140384 KB Time limit exceeded
36 Halted 0 ms 0 KB -