oj.uz

Submission #828858

# Submission time Handle Problem Language Result Execution time Memory
828858 2023-08-17T17:51:39 Z QwertyPi From Hacks to Snitches (BOI21_watchmen) C++14
15 / 100
 1297 ms 201780 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]});
				}
			}
		}
	}
	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 1273 ms 75752 KB Output is correct
2 Correct 84 ms 82356 KB Output is correct
3 Correct 74 ms 82496 KB Output is correct
4 Correct 1294 ms 81972 KB Output is correct
5 Correct 46 ms 74140 KB Output is correct
6 Correct 72 ms 82152 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 75744 KB Output is correct
2 Correct 79 ms 82496 KB Output is correct
3 Correct 77 ms 82452 KB Output is correct
4 Correct 1291 ms 81964 KB Output is correct
5 Correct 43 ms 74224 KB Output is correct
6 Correct 75 ms 82216 KB Output is correct
7 Correct 78 ms 82432 KB Output is correct
8 Correct 88 ms 82516 KB Output is correct
9 Correct 77 ms 82764 KB Output is correct
10 Correct 201 ms 81584 KB Output is correct
11 Correct 86 ms 81008 KB Output is correct
12 Correct 77 ms 82124 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 75744 KB Output is correct
2 Correct 79 ms 82496 KB Output is correct
3 Correct 77 ms 82452 KB Output is correct
4 Correct 1291 ms 81964 KB Output is correct
5 Correct 43 ms 74224 KB Output is correct
6 Correct 75 ms 82216 KB Output is correct
7 Correct 78 ms 82432 KB Output is correct
8 Correct 88 ms 82516 KB Output is correct
9 Correct 77 ms 82764 KB Output is correct
10 Correct 201 ms 81584 KB Output is correct
11 Correct 86 ms 81008 KB Output is correct
12 Correct 77 ms 82124 KB Output is correct
13 Correct 1288 ms 76344 KB Output is correct
14 Correct 78 ms 83528 KB Output is correct
15 Correct 77 ms 82392 KB Output is correct
16 Correct 1293 ms 82056 KB Output is correct
17 Correct 46 ms 74168 KB Output is correct
18 Correct 77 ms 82124 KB Output is correct
19 Correct 91 ms 82488 KB Output is correct
20 Correct 88 ms 82572 KB Output is correct
21 Correct 77 ms 82692 KB Output is correct
22 Correct 201 ms 81528 KB Output is correct
23 Correct 75 ms 81084 KB Output is correct
24 Correct 78 ms 82168 KB Output is correct
25 Runtime error 499 ms 201496 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 1288 ms 75744 KB Output is correct
2 Correct 79 ms 82496 KB Output is correct
3 Correct 77 ms 82452 KB Output is correct
4 Correct 1291 ms 81964 KB Output is correct
5 Correct 43 ms 74224 KB Output is correct
6 Correct 75 ms 82216 KB Output is correct
7 Correct 78 ms 82432 KB Output is correct
8 Correct 88 ms 82516 KB Output is correct
9 Correct 77 ms 82764 KB Output is correct
10 Correct 201 ms 81584 KB Output is correct
11 Correct 86 ms 81008 KB Output is correct
12 Correct 77 ms 82124 KB Output is correct
13 Correct 1288 ms 76344 KB Output is correct
14 Correct 78 ms 83528 KB Output is correct
15 Correct 77 ms 82392 KB Output is correct
16 Correct 1293 ms 82056 KB Output is correct
17 Correct 46 ms 74168 KB Output is correct
18 Correct 77 ms 82124 KB Output is correct
19 Correct 91 ms 82488 KB Output is correct
20 Correct 88 ms 82572 KB Output is correct
21 Correct 77 ms 82692 KB Output is correct
22 Correct 201 ms 81528 KB Output is correct
23 Correct 75 ms 81084 KB Output is correct
24 Correct 78 ms 82168 KB Output is correct
25 Runtime error 499 ms 201496 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 1273 ms 75752 KB Output is correct
2 Correct 84 ms 82356 KB Output is correct
3 Correct 74 ms 82496 KB Output is correct
4 Correct 1294 ms 81972 KB Output is correct
5 Correct 46 ms 74140 KB Output is correct
6 Correct 72 ms 82152 KB Output is correct
7 Correct 1288 ms 75744 KB Output is correct
8 Correct 79 ms 82496 KB Output is correct
9 Correct 77 ms 82452 KB Output is correct
10 Correct 1291 ms 81964 KB Output is correct
11 Correct 43 ms 74224 KB Output is correct
12 Correct 75 ms 82216 KB Output is correct
13 Correct 78 ms 82432 KB Output is correct
14 Correct 88 ms 82516 KB Output is correct
15 Correct 77 ms 82764 KB Output is correct
16 Correct 201 ms 81584 KB Output is correct
17 Correct 86 ms 81008 KB Output is correct
18 Correct 77 ms 82124 KB Output is correct
19 Correct 41 ms 73876 KB Output is correct
20 Correct 41 ms 73880 KB Output is correct
21 Correct 44 ms 73884 KB Output is correct
22 Correct 1277 ms 76340 KB Output is correct
23 Correct 85 ms 83572 KB Output is correct
24 Correct 85 ms 82480 KB Output is correct
25 Correct 1297 ms 82052 KB Output is correct
26 Correct 38 ms 74104 KB Output is correct
27 Correct 87 ms 82180 KB Output is correct
28 Correct 74 ms 82524 KB Output is correct
29 Correct 89 ms 82588 KB Output is correct
30 Correct 75 ms 82704 KB Output is correct
31 Correct 205 ms 81600 KB Output is correct
32 Correct 82 ms 81064 KB Output is correct
33 Correct 86 ms 82084 KB Output is correct
34 Runtime error 523 ms 201780 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 1273 ms 75752 KB Output is correct
2 Correct 84 ms 82356 KB Output is correct
3 Correct 74 ms 82496 KB Output is correct
4 Correct 1294 ms 81972 KB Output is correct
5 Correct 46 ms 74140 KB Output is correct
6 Correct 72 ms 82152 KB Output is correct
7 Correct 1288 ms 75744 KB Output is correct
8 Correct 79 ms 82496 KB Output is correct
9 Correct 77 ms 82452 KB Output is correct
10 Correct 1291 ms 81964 KB Output is correct
11 Correct 43 ms 74224 KB Output is correct
12 Correct 75 ms 82216 KB Output is correct
13 Correct 78 ms 82432 KB Output is correct
14 Correct 88 ms 82516 KB Output is correct
15 Correct 77 ms 82764 KB Output is correct
16 Correct 201 ms 81584 KB Output is correct
17 Correct 86 ms 81008 KB Output is correct
18 Correct 77 ms 82124 KB Output is correct
19 Correct 1288 ms 76344 KB Output is correct
20 Correct 78 ms 83528 KB Output is correct
21 Correct 77 ms 82392 KB Output is correct
22 Correct 1293 ms 82056 KB Output is correct
23 Correct 46 ms 74168 KB Output is correct
24 Correct 77 ms 82124 KB Output is correct
25 Correct 91 ms 82488 KB Output is correct
26 Correct 88 ms 82572 KB Output is correct
27 Correct 77 ms 82692 KB Output is correct
28 Correct 201 ms 81528 KB Output is correct
29 Correct 75 ms 81084 KB Output is correct
30 Correct 78 ms 82168 KB Output is correct
31 Runtime error 499 ms 201496 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 1273 ms 75752 KB Output is correct
2 Correct 84 ms 82356 KB Output is correct
3 Correct 74 ms 82496 KB Output is correct
4 Correct 1294 ms 81972 KB Output is correct
5 Correct 46 ms 74140 KB Output is correct
6 Correct 72 ms 82152 KB Output is correct
7 Correct 1288 ms 75744 KB Output is correct
8 Correct 79 ms 82496 KB Output is correct
9 Correct 77 ms 82452 KB Output is correct
10 Correct 1291 ms 81964 KB Output is correct
11 Correct 43 ms 74224 KB Output is correct
12 Correct 75 ms 82216 KB Output is correct
13 Correct 78 ms 82432 KB Output is correct
14 Correct 88 ms 82516 KB Output is correct
15 Correct 77 ms 82764 KB Output is correct
16 Correct 201 ms 81584 KB Output is correct
17 Correct 86 ms 81008 KB Output is correct
18 Correct 77 ms 82124 KB Output is correct
19 Correct 1288 ms 76344 KB Output is correct
20 Correct 78 ms 83528 KB Output is correct
21 Correct 77 ms 82392 KB Output is correct
22 Correct 1293 ms 82056 KB Output is correct
23 Correct 46 ms 74168 KB Output is correct
24 Correct 77 ms 82124 KB Output is correct
25 Correct 91 ms 82488 KB Output is correct
26 Correct 88 ms 82572 KB Output is correct
27 Correct 77 ms 82692 KB Output is correct
28 Correct 201 ms 81528 KB Output is correct
29 Correct 75 ms 81084 KB Output is correct
30 Correct 78 ms 82168 KB Output is correct
31 Runtime error 499 ms 201496 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -