oj.uz

Submission #409021

# Submission time Handle Problem Language Result Execution time Memory
409021 2021-05-20T05:19:10 Z Kevin_Zhang_TW From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 87456 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

using t3 = pair<ll,int>;
const int MAX_N = 300010, MAX_K = 2800;
const ll inf = 1ll << 55;

int n, m;
vector<int> edge[MAX_N], cyc[MAX_N];
vector<ll> dp[MAX_N];
int cid[MAX_N], csz[MAX_N], cpos[MAX_N];

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int a, b, i = 0;i < m;++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	for (int i = 1;i <= n;++i) {
		dp[i].resize(1, inf);
		csz[i] = 1;
	}
	int K;
	cin >> K;
	for (int i = 1;i <= K;++i) {
		int len;
		cin >> len;
		cyc[i].resize(len);
		int c = 0;
		for (int &u : cyc[i]) {
			cin >> u;
			cid[u] = i;
			csz[u] = len;
			cpos[u] = c++;
			dp[u].resize(len, inf);
			DE(u, cpos[u], len);
		}
	}

	priority_queue<t3, vector<t3>, greater<t3>> q;
	//queue<pair<int,ll>> q;

	auto upd = [&](int x, ll d) {
		DE(x, d);
		if (chmin(dp[x][d % csz[x]], d)) 
			q.emplace(d, x);
	};

	upd(1, 0);


	// shortest path

	// now there are no two cycle being connected
	// check if at x, time is d can move to 
	auto valid = [&](int x, ll d, int u) {
		if (cid[u] == 0) return true;
		if (d % csz[u] == cpos[u]) return false;
		if (cid[x] == 0) return true;
		assert(cid[x] == cid[u]);
		if (cpos[u] == (cpos[x] - 1 + csz[x]) % csz[u]) {
			if (d % csz[u] == cpos[x]) return false;
		}
		return true;
	};
	while (q.size()) {
		auto [d, x] = q.top(); q.pop();
		if (d != dp[x][ d % csz[x] ]) continue;
		if (cid[x]) {
			for (int u : edge[x]) {
				if (cid[u] == 0) {
					upd(u, d + 1);
					continue;
				}
				else {
					if (valid(x, d + 1, u))
						upd(u, d + 1);
				}
			}
			if (valid(x, d + 1, x))
				upd(x, d + 1);
		}
		else {
			for (int u : edge[x]) {
				if (cid[u] == 0) {
					upd(u, d + 1);
					continue;
				}
				else {
					for (int i = 1;i <= csz[u];++i)
						if (valid(x, d + i, u))
							upd(u, d + i);
				}
			}
		}
	}
	// 

	ll res = inf;
	for (auto v : dp[n]) chmin(res, v);
	
	if (res == inf) cout << "impossible\n";
	else cout << res << '\n';
}

Compilation message

watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
watchmen.cpp:52:4: note: in expansion of macro 'DE'
   52 |    DE(u, cpos[u], len);
      |    ^~
watchmen.cpp: In lambda function:
watchmen.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
watchmen.cpp:60:3: note: in expansion of macro 'DE'
   60 |   DE(x, d);
      |   ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 22732 KB Output is correct
2 Correct 85 ms 28728 KB Output is correct
3 Correct 94 ms 29540 KB Output is correct
4 Correct 123 ms 30016 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 104 ms 29580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22828 KB Output is correct
2 Correct 86 ms 28752 KB Output is correct
3 Correct 99 ms 29580 KB Output is correct
4 Correct 126 ms 30016 KB Output is correct
5 Correct 15 ms 21560 KB Output is correct
6 Correct 101 ms 29604 KB Output is correct
7 Correct 79 ms 29308 KB Output is correct
8 Correct 80 ms 29380 KB Output is correct
9 Correct 82 ms 29188 KB Output is correct
10 Correct 135 ms 29664 KB Output is correct
11 Correct 97 ms 29456 KB Output is correct
12 Correct 87 ms 29368 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22828 KB Output is correct
2 Correct 86 ms 28752 KB Output is correct
3 Correct 99 ms 29580 KB Output is correct
4 Correct 126 ms 30016 KB Output is correct
5 Correct 15 ms 21560 KB Output is correct
6 Correct 101 ms 29604 KB Output is correct
7 Correct 79 ms 29308 KB Output is correct
8 Correct 80 ms 29380 KB Output is correct
9 Correct 82 ms 29188 KB Output is correct
10 Correct 135 ms 29664 KB Output is correct
11 Correct 97 ms 29456 KB Output is correct
12 Correct 87 ms 29368 KB Output is correct
13 Correct 105 ms 23400 KB Output is correct
14 Correct 110 ms 29892 KB Output is correct
15 Correct 94 ms 29640 KB Output is correct
16 Correct 130 ms 30052 KB Output is correct
17 Correct 15 ms 21580 KB Output is correct
18 Correct 89 ms 29584 KB Output is correct
19 Correct 108 ms 29344 KB Output is correct
20 Correct 86 ms 29328 KB Output is correct
21 Correct 81 ms 29252 KB Output is correct
22 Correct 109 ms 29588 KB Output is correct
23 Correct 108 ms 29412 KB Output is correct
24 Correct 88 ms 29336 KB Output is correct
25 Correct 1948 ms 82340 KB Output is correct
26 Correct 1742 ms 87456 KB Output is correct
27 Correct 1708 ms 83624 KB Output is correct
28 Correct 1344 ms 86856 KB Output is correct
29 Execution timed out 6063 ms 78876 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22828 KB Output is correct
2 Correct 86 ms 28752 KB Output is correct
3 Correct 99 ms 29580 KB Output is correct
4 Correct 126 ms 30016 KB Output is correct
5 Correct 15 ms 21560 KB Output is correct
6 Correct 101 ms 29604 KB Output is correct
7 Correct 79 ms 29308 KB Output is correct
8 Correct 80 ms 29380 KB Output is correct
9 Correct 82 ms 29188 KB Output is correct
10 Correct 135 ms 29664 KB Output is correct
11 Correct 97 ms 29456 KB Output is correct
12 Correct 87 ms 29368 KB Output is correct
13 Correct 105 ms 23400 KB Output is correct
14 Correct 110 ms 29892 KB Output is correct
15 Correct 94 ms 29640 KB Output is correct
16 Correct 130 ms 30052 KB Output is correct
17 Correct 15 ms 21580 KB Output is correct
18 Correct 89 ms 29584 KB Output is correct
19 Correct 108 ms 29344 KB Output is correct
20 Correct 86 ms 29328 KB Output is correct
21 Correct 81 ms 29252 KB Output is correct
22 Correct 109 ms 29588 KB Output is correct
23 Correct 108 ms 29412 KB Output is correct
24 Correct 88 ms 29336 KB Output is correct
25 Correct 1948 ms 82340 KB Output is correct
26 Correct 1742 ms 87456 KB Output is correct
27 Correct 1708 ms 83624 KB Output is correct
28 Correct 1344 ms 86856 KB Output is correct
29 Execution timed out 6063 ms 78876 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 22732 KB Output is correct
2 Correct 85 ms 28728 KB Output is correct
3 Correct 94 ms 29540 KB Output is correct
4 Correct 123 ms 30016 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 104 ms 29580 KB Output is correct
7 Correct 103 ms 22828 KB Output is correct
8 Correct 86 ms 28752 KB Output is correct
9 Correct 99 ms 29580 KB Output is correct
10 Correct 126 ms 30016 KB Output is correct
11 Correct 15 ms 21560 KB Output is correct
12 Correct 101 ms 29604 KB Output is correct
13 Correct 79 ms 29308 KB Output is correct
14 Correct 80 ms 29380 KB Output is correct
15 Correct 82 ms 29188 KB Output is correct
16 Correct 135 ms 29664 KB Output is correct
17 Correct 97 ms 29456 KB Output is correct
18 Correct 87 ms 29368 KB Output is correct
19 Correct 12 ms 21452 KB Output is correct
20 Correct 13 ms 21432 KB Output is correct
21 Runtime error 36 ms 43300 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 22732 KB Output is correct
2 Correct 85 ms 28728 KB Output is correct
3 Correct 94 ms 29540 KB Output is correct
4 Correct 123 ms 30016 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 104 ms 29580 KB Output is correct
7 Correct 103 ms 22828 KB Output is correct
8 Correct 86 ms 28752 KB Output is correct
9 Correct 99 ms 29580 KB Output is correct
10 Correct 126 ms 30016 KB Output is correct
11 Correct 15 ms 21560 KB Output is correct
12 Correct 101 ms 29604 KB Output is correct
13 Correct 79 ms 29308 KB Output is correct
14 Correct 80 ms 29380 KB Output is correct
15 Correct 82 ms 29188 KB Output is correct
16 Correct 135 ms 29664 KB Output is correct
17 Correct 97 ms 29456 KB Output is correct
18 Correct 87 ms 29368 KB Output is correct
19 Correct 105 ms 23400 KB Output is correct
20 Correct 110 ms 29892 KB Output is correct
21 Correct 94 ms 29640 KB Output is correct
22 Correct 130 ms 30052 KB Output is correct
23 Correct 15 ms 21580 KB Output is correct
24 Correct 89 ms 29584 KB Output is correct
25 Correct 108 ms 29344 KB Output is correct
26 Correct 86 ms 29328 KB Output is correct
27 Correct 81 ms 29252 KB Output is correct
28 Correct 109 ms 29588 KB Output is correct
29 Correct 108 ms 29412 KB Output is correct
30 Correct 88 ms 29336 KB Output is correct
31 Correct 1948 ms 82340 KB Output is correct
32 Correct 1742 ms 87456 KB Output is correct
33 Correct 1708 ms 83624 KB Output is correct
34 Correct 1344 ms 86856 KB Output is correct
35 Execution timed out 6063 ms 78876 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 22732 KB Output is correct
2 Correct 85 ms 28728 KB Output is correct
3 Correct 94 ms 29540 KB Output is correct
4 Correct 123 ms 30016 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 104 ms 29580 KB Output is correct
7 Correct 103 ms 22828 KB Output is correct
8 Correct 86 ms 28752 KB Output is correct
9 Correct 99 ms 29580 KB Output is correct
10 Correct 126 ms 30016 KB Output is correct
11 Correct 15 ms 21560 KB Output is correct
12 Correct 101 ms 29604 KB Output is correct
13 Correct 79 ms 29308 KB Output is correct
14 Correct 80 ms 29380 KB Output is correct
15 Correct 82 ms 29188 KB Output is correct
16 Correct 135 ms 29664 KB Output is correct
17 Correct 97 ms 29456 KB Output is correct
18 Correct 87 ms 29368 KB Output is correct
19 Correct 105 ms 23400 KB Output is correct
20 Correct 110 ms 29892 KB Output is correct
21 Correct 94 ms 29640 KB Output is correct
22 Correct 130 ms 30052 KB Output is correct
23 Correct 15 ms 21580 KB Output is correct
24 Correct 89 ms 29584 KB Output is correct
25 Correct 108 ms 29344 KB Output is correct
26 Correct 86 ms 29328 KB Output is correct
27 Correct 81 ms 29252 KB Output is correct
28 Correct 109 ms 29588 KB Output is correct
29 Correct 108 ms 29412 KB Output is correct
30 Correct 88 ms 29336 KB Output is correct
31 Correct 1948 ms 82340 KB Output is correct
32 Correct 1742 ms 87456 KB Output is correct
33 Correct 1708 ms 83624 KB Output is correct
34 Correct 1344 ms 86856 KB Output is correct
35 Execution timed out 6063 ms 78876 KB Time limit exceeded
36 Halted 0 ms 0 KB -