Submission #409035

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409035	2021-05-20T05:44:16 Z	Kevin_Zhang_TW	From Hacks to Snitches (BOI21_watchmen)	C++17	15 / 100	6000 ms	81772 KB

watchmen

#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;

	vector<vector<int>> q;
	auto putin = [&](int d, int x) {
		if (q.size() < d + 1) q.resize(d + 1);
		q[d].pb(x);
	};

	auto upd = [&](int x, ll d) {
		if (chmin(dp[x][d % csz[x]], d)) 
			putin(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;
	};

	for (int d = 0;d < q.size();++d) {
		for (int i = 0;i < q[d].size();++i) {
			int x = q[d][i];
//
//	while (q.size()) {
//		//auto [d, x] = q.front(); q.pop();
//		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 {
				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);

						ll t = d + 1, m = t % csz[u];
						if (m != cpos[u]) {
							ll f = cpos[u] - m;
							if (f < 0) f += csz[u];
							t += f;
						}
						++t;
						if (valid(x, t, u))
							upd(u, t);
					}
				}
			}
		}
		vector<int>().swap(q[d]);
	}
	// 

	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:61:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |   if (q.size() < d + 1) q.resize(d + 1);
      |       ~~~~~~~~~^~~~~~~
watchmen.cpp: In function 'int32_t main()':
watchmen.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int d = 0;d < q.size();++d) {
      |                 ~~^~~~~~~~~~
watchmen.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = 0;i < q[d].size();++i) {
      |                  ~~^~~~~~~~~~~~~
watchmen.cpp:111:9: warning: unused variable 'mxc' [-Wunused-variable]
  111 |     int mxc = hol;
      |         ^~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	22332 KB	Output is correct
2	Correct	99 ms	31936 KB	Output is correct
3	Correct	85 ms	31236 KB	Output is correct
4	Correct	109 ms	29452 KB	Output is correct
5	Correct	14 ms	21612 KB	Output is correct
6	Correct	87 ms	30508 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	22468 KB	Output is correct
2	Correct	108 ms	31912 KB	Output is correct
3	Correct	89 ms	31336 KB	Output is correct
4	Correct	118 ms	29456 KB	Output is correct
5	Correct	13 ms	21540 KB	Output is correct
6	Correct	87 ms	30540 KB	Output is correct
7	Correct	100 ms	31328 KB	Output is correct
8	Correct	94 ms	31168 KB	Output is correct
9	Correct	90 ms	31168 KB	Output is correct
10	Correct	93 ms	28972 KB	Output is correct
11	Correct	79 ms	28652 KB	Output is correct
12	Correct	97 ms	29660 KB	Output is correct

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	22468 KB	Output is correct
2	Correct	108 ms	31912 KB	Output is correct
3	Correct	89 ms	31336 KB	Output is correct
4	Correct	118 ms	29456 KB	Output is correct
5	Correct	13 ms	21540 KB	Output is correct
6	Correct	87 ms	30540 KB	Output is correct
7	Correct	100 ms	31328 KB	Output is correct
8	Correct	94 ms	31168 KB	Output is correct
9	Correct	90 ms	31168 KB	Output is correct
10	Correct	93 ms	28972 KB	Output is correct
11	Correct	79 ms	28652 KB	Output is correct
12	Correct	97 ms	29660 KB	Output is correct
13	Correct	79 ms	22404 KB	Output is correct
14	Correct	102 ms	31888 KB	Output is correct
15	Correct	88 ms	31256 KB	Output is correct
16	Correct	109 ms	29472 KB	Output is correct
17	Correct	14 ms	21580 KB	Output is correct
18	Correct	86 ms	30580 KB	Output is correct
19	Correct	90 ms	31296 KB	Output is correct
20	Correct	94 ms	31252 KB	Output is correct
21	Correct	91 ms	31164 KB	Output is correct
22	Correct	94 ms	29000 KB	Output is correct
23	Correct	82 ms	28592 KB	Output is correct
24	Correct	85 ms	29644 KB	Output is correct
25	Correct	1824 ms	77436 KB	Output is correct
26	Correct	1726 ms	81772 KB	Output is correct
27	Correct	1618 ms	77740 KB	Output is correct
28	Correct	1318 ms	81764 KB	Output is correct
29	Execution timed out	6039 ms	66064 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	22468 KB	Output is correct
2	Correct	108 ms	31912 KB	Output is correct
3	Correct	89 ms	31336 KB	Output is correct
4	Correct	118 ms	29456 KB	Output is correct
5	Correct	13 ms	21540 KB	Output is correct
6	Correct	87 ms	30540 KB	Output is correct
7	Correct	100 ms	31328 KB	Output is correct
8	Correct	94 ms	31168 KB	Output is correct
9	Correct	90 ms	31168 KB	Output is correct
10	Correct	93 ms	28972 KB	Output is correct
11	Correct	79 ms	28652 KB	Output is correct
12	Correct	97 ms	29660 KB	Output is correct
13	Correct	79 ms	22404 KB	Output is correct
14	Correct	102 ms	31888 KB	Output is correct
15	Correct	88 ms	31256 KB	Output is correct
16	Correct	109 ms	29472 KB	Output is correct
17	Correct	14 ms	21580 KB	Output is correct
18	Correct	86 ms	30580 KB	Output is correct
19	Correct	90 ms	31296 KB	Output is correct
20	Correct	94 ms	31252 KB	Output is correct
21	Correct	91 ms	31164 KB	Output is correct
22	Correct	94 ms	29000 KB	Output is correct
23	Correct	82 ms	28592 KB	Output is correct
24	Correct	85 ms	29644 KB	Output is correct
25	Correct	1824 ms	77436 KB	Output is correct
26	Correct	1726 ms	81772 KB	Output is correct
27	Correct	1618 ms	77740 KB	Output is correct
28	Correct	1318 ms	81764 KB	Output is correct
29	Execution timed out	6039 ms	66064 KB	Time limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	22332 KB	Output is correct
2	Correct	99 ms	31936 KB	Output is correct
3	Correct	85 ms	31236 KB	Output is correct
4	Correct	109 ms	29452 KB	Output is correct
5	Correct	14 ms	21612 KB	Output is correct
6	Correct	87 ms	30508 KB	Output is correct
7	Correct	78 ms	22468 KB	Output is correct
8	Correct	108 ms	31912 KB	Output is correct
9	Correct	89 ms	31336 KB	Output is correct
10	Correct	118 ms	29456 KB	Output is correct
11	Correct	13 ms	21540 KB	Output is correct
12	Correct	87 ms	30540 KB	Output is correct
13	Correct	100 ms	31328 KB	Output is correct
14	Correct	94 ms	31168 KB	Output is correct
15	Correct	90 ms	31168 KB	Output is correct
16	Correct	93 ms	28972 KB	Output is correct
17	Correct	79 ms	28652 KB	Output is correct
18	Correct	97 ms	29660 KB	Output is correct
19	Correct	13 ms	21452 KB	Output is correct
20	Correct	13 ms	21452 KB	Output is correct
21	Runtime error	34 ms	43316 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	78 ms	22332 KB	Output is correct
2	Correct	99 ms	31936 KB	Output is correct
3	Correct	85 ms	31236 KB	Output is correct
4	Correct	109 ms	29452 KB	Output is correct
5	Correct	14 ms	21612 KB	Output is correct
6	Correct	87 ms	30508 KB	Output is correct
7	Correct	78 ms	22468 KB	Output is correct
8	Correct	108 ms	31912 KB	Output is correct
9	Correct	89 ms	31336 KB	Output is correct
10	Correct	118 ms	29456 KB	Output is correct
11	Correct	13 ms	21540 KB	Output is correct
12	Correct	87 ms	30540 KB	Output is correct
13	Correct	100 ms	31328 KB	Output is correct
14	Correct	94 ms	31168 KB	Output is correct
15	Correct	90 ms	31168 KB	Output is correct
16	Correct	93 ms	28972 KB	Output is correct
17	Correct	79 ms	28652 KB	Output is correct
18	Correct	97 ms	29660 KB	Output is correct
19	Correct	79 ms	22404 KB	Output is correct
20	Correct	102 ms	31888 KB	Output is correct
21	Correct	88 ms	31256 KB	Output is correct
22	Correct	109 ms	29472 KB	Output is correct
23	Correct	14 ms	21580 KB	Output is correct
24	Correct	86 ms	30580 KB	Output is correct
25	Correct	90 ms	31296 KB	Output is correct
26	Correct	94 ms	31252 KB	Output is correct
27	Correct	91 ms	31164 KB	Output is correct
28	Correct	94 ms	29000 KB	Output is correct
29	Correct	82 ms	28592 KB	Output is correct
30	Correct	85 ms	29644 KB	Output is correct
31	Correct	1824 ms	77436 KB	Output is correct
32	Correct	1726 ms	81772 KB	Output is correct
33	Correct	1618 ms	77740 KB	Output is correct
34	Correct	1318 ms	81764 KB	Output is correct
35	Execution timed out	6039 ms	66064 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	22332 KB	Output is correct
2	Correct	99 ms	31936 KB	Output is correct
3	Correct	85 ms	31236 KB	Output is correct
4	Correct	109 ms	29452 KB	Output is correct
5	Correct	14 ms	21612 KB	Output is correct
6	Correct	87 ms	30508 KB	Output is correct
7	Correct	78 ms	22468 KB	Output is correct
8	Correct	108 ms	31912 KB	Output is correct
9	Correct	89 ms	31336 KB	Output is correct
10	Correct	118 ms	29456 KB	Output is correct
11	Correct	13 ms	21540 KB	Output is correct
12	Correct	87 ms	30540 KB	Output is correct
13	Correct	100 ms	31328 KB	Output is correct
14	Correct	94 ms	31168 KB	Output is correct
15	Correct	90 ms	31168 KB	Output is correct
16	Correct	93 ms	28972 KB	Output is correct
17	Correct	79 ms	28652 KB	Output is correct
18	Correct	97 ms	29660 KB	Output is correct
19	Correct	79 ms	22404 KB	Output is correct
20	Correct	102 ms	31888 KB	Output is correct
21	Correct	88 ms	31256 KB	Output is correct
22	Correct	109 ms	29472 KB	Output is correct
23	Correct	14 ms	21580 KB	Output is correct
24	Correct	86 ms	30580 KB	Output is correct
25	Correct	90 ms	31296 KB	Output is correct
26	Correct	94 ms	31252 KB	Output is correct
27	Correct	91 ms	31164 KB	Output is correct
28	Correct	94 ms	29000 KB	Output is correct
29	Correct	82 ms	28592 KB	Output is correct
30	Correct	85 ms	29644 KB	Output is correct
31	Correct	1824 ms	77436 KB	Output is correct
32	Correct	1726 ms	81772 KB	Output is correct
33	Correct	1618 ms	77740 KB	Output is correct
34	Correct	1318 ms	81764 KB	Output is correct
35	Execution timed out	6039 ms	66064 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-