oj.uz

답안 #409035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409035 2021-05-20T05:44:16 Z Kevin_Zhang_TW From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 81772 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;

	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -