oj.uz

Submission #409020

# Submission time Handle Problem Language Result Execution time Memory
409020 2021-05-20T05:16:07 Z Kevin_Zhang_TW From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 102 ms 29932 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])) {
			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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23328 KB Output is correct
2 Incorrect 88 ms 29932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 23372 KB Output is correct
2 Incorrect 88 ms 29920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 23372 KB Output is correct
2 Incorrect 88 ms 29920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 23372 KB Output is correct
2 Incorrect 88 ms 29920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23328 KB Output is correct
2 Incorrect 88 ms 29932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23328 KB Output is correct
2 Incorrect 88 ms 29932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 23328 KB Output is correct
2 Incorrect 88 ms 29932 KB Output isn't correct
3 Halted 0 ms 0 KB -