oj.uz

Submission #828860

# Submission time Handle Problem Language Result Execution time Memory
828860 2023-08-17T17:53:00 Z QwertyPi From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 1293 ms 163340 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 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{
						for(int j = 0; j < cl[u]; 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:116:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  116 |     if(vis2[vi[v]][d % cl[v]]) continue; vis2[vi[v]][d % cl[v]] = true;
      |     ^~
watchmen.cpp:116:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  116 |     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 1280 ms 75760 KB Output is correct
2 Correct 79 ms 82452 KB Output is correct
3 Correct 79 ms 81260 KB Output is correct
4 Correct 1281 ms 80892 KB Output is correct
5 Correct 39 ms 74180 KB Output is correct
6 Correct 73 ms 81052 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 75764 KB Output is correct
2 Correct 77 ms 82368 KB Output is correct
3 Correct 73 ms 81288 KB Output is correct
4 Correct 1283 ms 80804 KB Output is correct
5 Correct 40 ms 74196 KB Output is correct
6 Correct 72 ms 80968 KB Output is correct
7 Correct 74 ms 81376 KB Output is correct
8 Correct 77 ms 81380 KB Output is correct
9 Correct 74 ms 81540 KB Output is correct
10 Correct 197 ms 80352 KB Output is correct
11 Correct 74 ms 79856 KB Output is correct
12 Correct 93 ms 81044 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 75764 KB Output is correct
2 Correct 77 ms 82368 KB Output is correct
3 Correct 73 ms 81288 KB Output is correct
4 Correct 1283 ms 80804 KB Output is correct
5 Correct 40 ms 74196 KB Output is correct
6 Correct 72 ms 80968 KB Output is correct
7 Correct 74 ms 81376 KB Output is correct
8 Correct 77 ms 81380 KB Output is correct
9 Correct 74 ms 81540 KB Output is correct
10 Correct 197 ms 80352 KB Output is correct
11 Correct 74 ms 79856 KB Output is correct
12 Correct 93 ms 81044 KB Output is correct
13 Correct 1275 ms 75756 KB Output is correct
14 Correct 78 ms 82376 KB Output is correct
15 Correct 103 ms 81276 KB Output is correct
16 Correct 1286 ms 80808 KB Output is correct
17 Correct 40 ms 74196 KB Output is correct
18 Correct 74 ms 81008 KB Output is correct
19 Correct 75 ms 81344 KB Output is correct
20 Correct 75 ms 81356 KB Output is correct
21 Correct 78 ms 81640 KB Output is correct
22 Correct 199 ms 80396 KB Output is correct
23 Correct 76 ms 79896 KB Output is correct
24 Correct 74 ms 80964 KB Output is correct
25 Runtime error 476 ms 163044 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 75764 KB Output is correct
2 Correct 77 ms 82368 KB Output is correct
3 Correct 73 ms 81288 KB Output is correct
4 Correct 1283 ms 80804 KB Output is correct
5 Correct 40 ms 74196 KB Output is correct
6 Correct 72 ms 80968 KB Output is correct
7 Correct 74 ms 81376 KB Output is correct
8 Correct 77 ms 81380 KB Output is correct
9 Correct 74 ms 81540 KB Output is correct
10 Correct 197 ms 80352 KB Output is correct
11 Correct 74 ms 79856 KB Output is correct
12 Correct 93 ms 81044 KB Output is correct
13 Correct 1275 ms 75756 KB Output is correct
14 Correct 78 ms 82376 KB Output is correct
15 Correct 103 ms 81276 KB Output is correct
16 Correct 1286 ms 80808 KB Output is correct
17 Correct 40 ms 74196 KB Output is correct
18 Correct 74 ms 81008 KB Output is correct
19 Correct 75 ms 81344 KB Output is correct
20 Correct 75 ms 81356 KB Output is correct
21 Correct 78 ms 81640 KB Output is correct
22 Correct 199 ms 80396 KB Output is correct
23 Correct 76 ms 79896 KB Output is correct
24 Correct 74 ms 80964 KB Output is correct
25 Runtime error 476 ms 163044 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1280 ms 75760 KB Output is correct
2 Correct 79 ms 82452 KB Output is correct
3 Correct 79 ms 81260 KB Output is correct
4 Correct 1281 ms 80892 KB Output is correct
5 Correct 39 ms 74180 KB Output is correct
6 Correct 73 ms 81052 KB Output is correct
7 Correct 1276 ms 75764 KB Output is correct
8 Correct 77 ms 82368 KB Output is correct
9 Correct 73 ms 81288 KB Output is correct
10 Correct 1283 ms 80804 KB Output is correct
11 Correct 40 ms 74196 KB Output is correct
12 Correct 72 ms 80968 KB Output is correct
13 Correct 74 ms 81376 KB Output is correct
14 Correct 77 ms 81380 KB Output is correct
15 Correct 74 ms 81540 KB Output is correct
16 Correct 197 ms 80352 KB Output is correct
17 Correct 74 ms 79856 KB Output is correct
18 Correct 93 ms 81044 KB Output is correct
19 Correct 40 ms 73760 KB Output is correct
20 Correct 39 ms 73820 KB Output is correct
21 Correct 41 ms 73820 KB Output is correct
22 Correct 1273 ms 75712 KB Output is correct
23 Correct 76 ms 82448 KB Output is correct
24 Correct 76 ms 81280 KB Output is correct
25 Correct 1293 ms 80808 KB Output is correct
26 Correct 41 ms 74196 KB Output is correct
27 Correct 73 ms 81004 KB Output is correct
28 Correct 75 ms 81344 KB Output is correct
29 Correct 79 ms 81440 KB Output is correct
30 Correct 75 ms 81608 KB Output is correct
31 Correct 200 ms 80448 KB Output is correct
32 Correct 77 ms 79872 KB Output is correct
33 Correct 73 ms 81020 KB Output is correct
34 Runtime error 498 ms 163340 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1280 ms 75760 KB Output is correct
2 Correct 79 ms 82452 KB Output is correct
3 Correct 79 ms 81260 KB Output is correct
4 Correct 1281 ms 80892 KB Output is correct
5 Correct 39 ms 74180 KB Output is correct
6 Correct 73 ms 81052 KB Output is correct
7 Correct 1276 ms 75764 KB Output is correct
8 Correct 77 ms 82368 KB Output is correct
9 Correct 73 ms 81288 KB Output is correct
10 Correct 1283 ms 80804 KB Output is correct
11 Correct 40 ms 74196 KB Output is correct
12 Correct 72 ms 80968 KB Output is correct
13 Correct 74 ms 81376 KB Output is correct
14 Correct 77 ms 81380 KB Output is correct
15 Correct 74 ms 81540 KB Output is correct
16 Correct 197 ms 80352 KB Output is correct
17 Correct 74 ms 79856 KB Output is correct
18 Correct 93 ms 81044 KB Output is correct
19 Correct 1275 ms 75756 KB Output is correct
20 Correct 78 ms 82376 KB Output is correct
21 Correct 103 ms 81276 KB Output is correct
22 Correct 1286 ms 80808 KB Output is correct
23 Correct 40 ms 74196 KB Output is correct
24 Correct 74 ms 81008 KB Output is correct
25 Correct 75 ms 81344 KB Output is correct
26 Correct 75 ms 81356 KB Output is correct
27 Correct 78 ms 81640 KB Output is correct
28 Correct 199 ms 80396 KB Output is correct
29 Correct 76 ms 79896 KB Output is correct
30 Correct 74 ms 80964 KB Output is correct
31 Runtime error 476 ms 163044 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1280 ms 75760 KB Output is correct
2 Correct 79 ms 82452 KB Output is correct
3 Correct 79 ms 81260 KB Output is correct
4 Correct 1281 ms 80892 KB Output is correct
5 Correct 39 ms 74180 KB Output is correct
6 Correct 73 ms 81052 KB Output is correct
7 Correct 1276 ms 75764 KB Output is correct
8 Correct 77 ms 82368 KB Output is correct
9 Correct 73 ms 81288 KB Output is correct
10 Correct 1283 ms 80804 KB Output is correct
11 Correct 40 ms 74196 KB Output is correct
12 Correct 72 ms 80968 KB Output is correct
13 Correct 74 ms 81376 KB Output is correct
14 Correct 77 ms 81380 KB Output is correct
15 Correct 74 ms 81540 KB Output is correct
16 Correct 197 ms 80352 KB Output is correct
17 Correct 74 ms 79856 KB Output is correct
18 Correct 93 ms 81044 KB Output is correct
19 Correct 1275 ms 75756 KB Output is correct
20 Correct 78 ms 82376 KB Output is correct
21 Correct 103 ms 81276 KB Output is correct
22 Correct 1286 ms 80808 KB Output is correct
23 Correct 40 ms 74196 KB Output is correct
24 Correct 74 ms 81008 KB Output is correct
25 Correct 75 ms 81344 KB Output is correct
26 Correct 75 ms 81356 KB Output is correct
27 Correct 78 ms 81640 KB Output is correct
28 Correct 199 ms 80396 KB Output is correct
29 Correct 76 ms 79896 KB Output is correct
30 Correct 74 ms 80964 KB Output is correct
31 Runtime error 476 ms 163044 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -