oj.uz

Submission #409031

# Submission time Handle Problem Language Result Execution time Memory
409031 2021-05-20T05:32:03 Z Kevin_Zhang_TW From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 71780 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, hol = 100;
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<ll,int>> 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.front(); 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 {
			int mxc = hol;
			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);
//					for (int i = 1;i <= csz[u];++i)
//						if (valid(x, d + i, u))
//							upd(u, d + i);
				}
			}
			if (d - dp[x][0] < mxc)
				q.emplace(d + 1, x);
		}
	}
	// 

	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 158 ms 22340 KB Output is correct
2 Correct 449 ms 29008 KB Output is correct
3 Correct 730 ms 28500 KB Output is correct
4 Correct 991 ms 29012 KB Output is correct
5 Correct 14 ms 21580 KB Output is correct
6 Correct 823 ms 28612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 22440 KB Output is correct
2 Correct 439 ms 28816 KB Output is correct
3 Correct 694 ms 28508 KB Output is correct
4 Correct 1066 ms 28980 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 932 ms 28608 KB Output is correct
7 Correct 622 ms 28340 KB Output is correct
8 Correct 540 ms 28184 KB Output is correct
9 Correct 450 ms 28052 KB Output is correct
10 Correct 863 ms 28696 KB Output is correct
11 Correct 830 ms 28372 KB Output is correct
12 Correct 862 ms 28612 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 22440 KB Output is correct
2 Correct 439 ms 28816 KB Output is correct
3 Correct 694 ms 28508 KB Output is correct
4 Correct 1066 ms 28980 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 932 ms 28608 KB Output is correct
7 Correct 622 ms 28340 KB Output is correct
8 Correct 540 ms 28184 KB Output is correct
9 Correct 450 ms 28052 KB Output is correct
10 Correct 863 ms 28696 KB Output is correct
11 Correct 830 ms 28372 KB Output is correct
12 Correct 862 ms 28612 KB Output is correct
13 Correct 154 ms 22312 KB Output is correct
14 Correct 439 ms 28776 KB Output is correct
15 Correct 719 ms 28500 KB Output is correct
16 Correct 1078 ms 29088 KB Output is correct
17 Correct 16 ms 21580 KB Output is correct
18 Correct 840 ms 28640 KB Output is correct
19 Correct 586 ms 28228 KB Output is correct
20 Correct 516 ms 28248 KB Output is correct
21 Correct 449 ms 28148 KB Output is correct
22 Correct 883 ms 28684 KB Output is correct
23 Correct 782 ms 28268 KB Output is correct
24 Correct 803 ms 28536 KB Output is correct
25 Execution timed out 6063 ms 71780 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 22440 KB Output is correct
2 Correct 439 ms 28816 KB Output is correct
3 Correct 694 ms 28508 KB Output is correct
4 Correct 1066 ms 28980 KB Output is correct
5 Correct 15 ms 21580 KB Output is correct
6 Correct 932 ms 28608 KB Output is correct
7 Correct 622 ms 28340 KB Output is correct
8 Correct 540 ms 28184 KB Output is correct
9 Correct 450 ms 28052 KB Output is correct
10 Correct 863 ms 28696 KB Output is correct
11 Correct 830 ms 28372 KB Output is correct
12 Correct 862 ms 28612 KB Output is correct
13 Correct 154 ms 22312 KB Output is correct
14 Correct 439 ms 28776 KB Output is correct
15 Correct 719 ms 28500 KB Output is correct
16 Correct 1078 ms 29088 KB Output is correct
17 Correct 16 ms 21580 KB Output is correct
18 Correct 840 ms 28640 KB Output is correct
19 Correct 586 ms 28228 KB Output is correct
20 Correct 516 ms 28248 KB Output is correct
21 Correct 449 ms 28148 KB Output is correct
22 Correct 883 ms 28684 KB Output is correct
23 Correct 782 ms 28268 KB Output is correct
24 Correct 803 ms 28536 KB Output is correct
25 Execution timed out 6063 ms 71780 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 22340 KB Output is correct
2 Correct 449 ms 29008 KB Output is correct
3 Correct 730 ms 28500 KB Output is correct
4 Correct 991 ms 29012 KB Output is correct
5 Correct 14 ms 21580 KB Output is correct
6 Correct 823 ms 28612 KB Output is correct
7 Correct 156 ms 22440 KB Output is correct
8 Correct 439 ms 28816 KB Output is correct
9 Correct 694 ms 28508 KB Output is correct
10 Correct 1066 ms 28980 KB Output is correct
11 Correct 15 ms 21580 KB Output is correct
12 Correct 932 ms 28608 KB Output is correct
13 Correct 622 ms 28340 KB Output is correct
14 Correct 540 ms 28184 KB Output is correct
15 Correct 450 ms 28052 KB Output is correct
16 Correct 863 ms 28696 KB Output is correct
17 Correct 830 ms 28372 KB Output is correct
18 Correct 862 ms 28612 KB Output is correct
19 Correct 14 ms 21464 KB Output is correct
20 Correct 12 ms 21460 KB Output is correct
21 Runtime error 37 ms 43340 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 158 ms 22340 KB Output is correct
2 Correct 449 ms 29008 KB Output is correct
3 Correct 730 ms 28500 KB Output is correct
4 Correct 991 ms 29012 KB Output is correct
5 Correct 14 ms 21580 KB Output is correct
6 Correct 823 ms 28612 KB Output is correct
7 Correct 156 ms 22440 KB Output is correct
8 Correct 439 ms 28816 KB Output is correct
9 Correct 694 ms 28508 KB Output is correct
10 Correct 1066 ms 28980 KB Output is correct
11 Correct 15 ms 21580 KB Output is correct
12 Correct 932 ms 28608 KB Output is correct
13 Correct 622 ms 28340 KB Output is correct
14 Correct 540 ms 28184 KB Output is correct
15 Correct 450 ms 28052 KB Output is correct
16 Correct 863 ms 28696 KB Output is correct
17 Correct 830 ms 28372 KB Output is correct
18 Correct 862 ms 28612 KB Output is correct
19 Correct 154 ms 22312 KB Output is correct
20 Correct 439 ms 28776 KB Output is correct
21 Correct 719 ms 28500 KB Output is correct
22 Correct 1078 ms 29088 KB Output is correct
23 Correct 16 ms 21580 KB Output is correct
24 Correct 840 ms 28640 KB Output is correct
25 Correct 586 ms 28228 KB Output is correct
26 Correct 516 ms 28248 KB Output is correct
27 Correct 449 ms 28148 KB Output is correct
28 Correct 883 ms 28684 KB Output is correct
29 Correct 782 ms 28268 KB Output is correct
30 Correct 803 ms 28536 KB Output is correct
31 Execution timed out 6063 ms 71780 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 22340 KB Output is correct
2 Correct 449 ms 29008 KB Output is correct
3 Correct 730 ms 28500 KB Output is correct
4 Correct 991 ms 29012 KB Output is correct
5 Correct 14 ms 21580 KB Output is correct
6 Correct 823 ms 28612 KB Output is correct
7 Correct 156 ms 22440 KB Output is correct
8 Correct 439 ms 28816 KB Output is correct
9 Correct 694 ms 28508 KB Output is correct
10 Correct 1066 ms 28980 KB Output is correct
11 Correct 15 ms 21580 KB Output is correct
12 Correct 932 ms 28608 KB Output is correct
13 Correct 622 ms 28340 KB Output is correct
14 Correct 540 ms 28184 KB Output is correct
15 Correct 450 ms 28052 KB Output is correct
16 Correct 863 ms 28696 KB Output is correct
17 Correct 830 ms 28372 KB Output is correct
18 Correct 862 ms 28612 KB Output is correct
19 Correct 154 ms 22312 KB Output is correct
20 Correct 439 ms 28776 KB Output is correct
21 Correct 719 ms 28500 KB Output is correct
22 Correct 1078 ms 29088 KB Output is correct
23 Correct 16 ms 21580 KB Output is correct
24 Correct 840 ms 28640 KB Output is correct
25 Correct 586 ms 28228 KB Output is correct
26 Correct 516 ms 28248 KB Output is correct
27 Correct 449 ms 28148 KB Output is correct
28 Correct 883 ms 28684 KB Output is correct
29 Correct 782 ms 28268 KB Output is correct
30 Correct 803 ms 28536 KB Output is correct
31 Execution timed out 6063 ms 71780 KB Time limit exceeded
32 Halted 0 ms 0 KB -