Submission #1270163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270163		MateiKing80	Board Game (JOI24_boardgame)	C++20	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int inf = 1e18;
const int BULAN = 100;

using pii = pair<int, int>;
#define fr first
#define sc second

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<int>> vec(n);
	vector<bool> stop(n);
	for (int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		u --, v --;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int nrStop = 0;
	for (int i = 0; i < n; i ++) {
		char ch;
		cin >> ch;
		stop[i] = ch - '0';
		nrStop += stop[i];
	}
	
	if (nrStop <= 
	
	vector<int> start(k);
	for (int i = 0; i < k; i ++) {
		cin >> start[i];
		start[i] --;
	}
	vector<int> distStart(n, inf), dp(n, 0);
	distStart[start[0]] = 0;
	queue<int> st;
	st.push(start[0]);
	vector<bool> viz(n, false);
	while (!st.empty()) {
		int x = st.front();
		st.pop();
		if ((x != start[0] && stop[x]) || viz[x])
			continue;
		viz[x] = true;
		for (auto i : vec[x]) {
			distStart[i] = min(distStart[i], 1 + distStart[x]);
			st.push(i);
		}
	}
	vector<int> ans(n, inf);
	
	vector<bool> doubleStop(n, false);
	for (int i = 0; i < n; i ++) {
		for (auto j : vec[i])
			if (stop[i] && stop[j])
				doubleStop[i] = true;
	}
	
	vector<int> init(n, inf);
	for (int i = 0; i < n; i ++)
		if (stop[i]) {
			st.push(i);
			init[i] = 0;
		}
	viz.assign(n, 0);
	while (!st.empty()) {
		int x = st.front();
		st.pop();
		if (viz[x])
			continue;
		viz[x] = true;
		for (auto i : vec[x]) {
			init[i] = min(init[i], init[x] + 1);
			st.push(i);
		}
	}
	
	for (auto &i : init)
		if (i == 0)
			i += 2;
	for (int i = 0; i < n; i ++)
		if (doubleStop[i])
			init[i] --;
	
	deque<int> dq;
	vector<int> init2(n, inf);
	
	for (int i = 0; i < n; i ++)
		if (doubleStop[i]) {
			init2[i] = 0;
			dq.push_back(i);
		}
	viz.assign(n, 0);
	while (!dq.empty()) {
		int x = dq.front();
		dq.pop_front();
		if (viz[x])
			continue;
		viz[x] = true;
		for (auto i : vec[x]) {
			int cost = (stop[x] == 0);
			init2[i] = min(init2[i], init2[x] + cost);
			if (cost)
				dq.push_back(i);
			else
				dq.push_front(i);
		}
	}
	
	vector<int> schimb;
	for (int i = 1; i < k; i ++)
		schimb.push_back(init2[start[i]] - init[start[i]] + 2);
	int add = 2 * (k - 1), point = 0;
	sort(schimb.begin(), schimb.end());
	int sum = 0;
	vector<int> cost(n + 1);
	for (int rep = 0; rep <= n; rep ++) {
		if (rep == 1)
			for (int i = 1; i < k; i ++)
				sum += init[start[i]];
		if (rep > 1)
			sum += add;
		if (rep >= 1) {
			while (point < (int)schimb.size() && schimb[point] <= rep) {
				add --;
				point ++;
			}
		}
		cost[rep] = sum;
	}

	for (int i = 0; i < n; i ++)
		ans[i] = min(ans[i], distStart[i]);
	
	if (k <= BULAN || nrStop <= 1) {
		for (int cst = k; cst <= 2 * k - 1; cst ++) {
			priority_queue<pair<int, int>> pq;
			pq.push({0, start[0]});
			vector<pair<int, int>> dist(n, {inf, 0});
			dist[start[0]] = {0, 0};
			viz.assign(n, 0);
			while (!pq.empty()) {
				int x = pq.top().second;
				pq.pop();
				if (viz[x])
					continue;
				viz[x] = true;
				for (auto i : vec[x]) {
					if (stop[x] && x != start[0]) {
						dist[i] = min(dist[i], {dist[x].first + cst, dist[x].second + 1});
					} else {
						dist[i] = min(dist[i], {dist[x].first + 1, dist[x].second});
					}
					pq.push({-dist[i].first, i});
				}
			}
			for (int i = 0; i < n; i ++)
				ans[i] = min(ans[i], cost[dist[i].second] + dist[i].first - (cst - 1) * dist[i].second);
		}
	} else {
		dq.clear();
		dq.push_back(start[0]);
		vector<int> dist(n, inf);
		dist[start[0]] = 0;
		viz.assign(n, 0);
		while (!dq.empty()) {
			int x = dq.front();
			dq.pop_front();
			if (viz[x])
				continue;
			viz[x] = true;
			for (auto i : vec[x]) {
				if (stop[x] && x != start[0]) {
					dist[i] = min(dist[i], dist[x] + 1);
					dq.push_back(i);
				} else {
					dist[i] = min(dist[i], dist[x]);
					dq.push_front(i);
				}
			}
		}
		int upper = n / (k - 1) + 5;
		queue<pair<int, int>> q;
		q.push({start[0], 0});
		vector<vector<int>> dst(n, vector<int> (upper, inf));
		dst[start[0]][0] = 0;
		vector<vector<bool>> vz(n, vector<bool> (upper, false));
		while (!q.empty()) {
			int nod = q.front().first;
			int nrx = q.front().second;
			q.pop();
			if (vz[nod][nrx - dist[nod]])
				continue;
			vz[nod][nrx - dist[nod]] = true;
			for (auto i : vec[nod]) {
				if (stop[nod] && nod != start[0]) {
					if (nrx + 1 < dist[i] + upper) {
						dst[i][nrx + 1 - dist[i]] = min(dst[i][nrx + 1 - dist[i]], dst[nod][nrx - dist[nod]] + 1);
						q.push({i, nrx + 1});
					}
				} else {
					if (nrx < dist[i] + upper) {
						dst[i][nrx - dist[i]] = min(dst[i][nrx - dist[i]], dst[nod][nrx - dist[nod]] + 1);
						q.push({i, nrx});
					}
				}
			}
		}
		for (int i = 0; i < n; i ++)
			for (int j = 0; j < upper; j ++)
				if (j + dist[i] <= n)
					ans[i] = min(ans[i], cost[j + dist[i]] + dst[i][j]);
	}
	for (int i = 0; i < n; i ++)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:21: error: expected primary-expression before 'start'
   39 |         vector<int> start(k);
      |                     ^~~~~
Main.cpp:40:9: error: expected primary-expression before 'for'
   40 |         for (int i = 0; i < k; i ++) {
      |         ^~~
Main.cpp:39:30: error: expected ')' before 'for'
   39 |         vector<int> start(k);
      |                              ^
      |                              )
   40 |         for (int i = 0; i < k; i ++) {
      |         ~~~                   
Main.cpp:37:12: note: to match this '('
   37 |         if (nrStop <=
      |            ^
Main.cpp:40:25: error: 'i' was not declared in this scope
   40 |         for (int i = 0; i < k; i ++) {
      |                         ^
Main.cpp:45:19: error: 'start' was not declared in this scope
   45 |         distStart[start[0]] = 0;
      |                   ^~~~~
Main.cpp:148:32: error: no matching function for call to 'std::priority_queue<std::pair<long long int, long long int> >::push(<brace-enclosed initializer list>)'
  148 |                         pq.push({0, start[0]});
      |                         ~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/queue:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157,
                 from Main.cpp:1:
/usr/include/c++/13/bits/stl_queue.h:738:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >; _Compare = std::less<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
  738 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/13/bits/stl_queue.h:738:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::priority_queue<std::pair<long long int, long long int> >::value_type&' {aka 'const std::pair<long long int, long long int>&'}
  738 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_queue.h:746:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(value_type&&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >; _Compare = std::less<std::pair<long long int, long long int> >; value_type = std::pair<long long int, long long int>]'
  746 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/13/bits/stl_queue.h:746:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
  746 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
Main.cpp:194:23: error: no matching function for call to 'std::queue<std::pair<long long int, long long int> >::push(<brace-enclosed initializer list>)'
  194 |                 q.push({start[0], 0});
      |                 ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_queue.h:285:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::deque<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >; value_type = std::pair<long long int, long long int>]'
  285 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/13/bits/stl_queue.h:285:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::queue<std::pair<long long int, long long int> >::value_type&' {aka 'const std::pair<long long int, long long int>&'}
  285 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_queue.h:290:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(value_type&&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::deque<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >; value_type = std::pair<long long int, long long int>]'
  290 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/13/bits/stl_queue.h:290:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::queue<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
  290 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~