Submission #1368601

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

Main

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define INF 100000000000LL

vector<vector<signed>> adjlist;
vector<signed> start;

signed main() {
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, M, K, a, b; cin >> N >> M >> K;
	adjlist.resize(N, vector<signed>());
	for (int i = 0; i < M; i++) {
		cin >> a >> b; a--, b--;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	string S; cin >> S;
	for (int i = 0; i < K; i++) {
		cin >> a; a--;
		start.push_back(a);
	}
	int esum = 0;
	for (char i : S) esum += (i - '0');
	if (esum == 0) {
		vector<int> dist(N, INF);
		queue<int> bfs;
		dist[start[0]] = 0;
		bfs.push(start[0]);
		while (bfs.size()) {
			int i = bfs.front(); bfs.pop();
			for (int j : adjlist[i]) {
				if (dist[j] != INF) continue;
				dist[j] = dist[i] + 1;
				bfs.push(j);
			}
		}
		for (int i : dist) cout << i << '\n';
		return 0;
	}
	/*
	vector<vector<int>> dist(N, vector<int>(N, INF));
	queue<pair<int, int>> bfs;
	dist[0][start[0]] = 0;
	bfs.push({start[0], 0});
	while (bfs.size()) {
		auto i = bfs.front(); bfs.pop();
		if (i.second == N - 1) continue;
		int od = dist[i.second][i.first];
		if ((i.first != start[0] || i.second) && S[i.first] == '1') i.second++;
		for (int j : adjlist[i.first]) {
			if (dist[i.second][j] != INF) continue;
			dist[i.second][j] = od + 1;
			bfs.push({j, i.second});
		}
	}
	*/
	bitset<50000> spec = 0;
	for (int i = 0; i < N; i++) {
		if (S[i] == '0') continue;
		for (int j : adjlist[i]) if (S[j] == '1') spec[i] = 1;
	}
	vector<signed> A(K, N + 10), B(K, N + 10);
	A[0] = 0;
	vector<signed> dist1(N, N + 10);
	for (signed i = 1; i < K; i++) {
		fill(dist1.begin(), dist1.end(), INF);
		deque<signed> bfs1;
		dist1[start[i]] = 0;
		bfs1.push_front(start[i]);
		while (bfs1.size()) {
			signed j = bfs1.front(); bfs1.pop_front();
			if (j != start[i] && S[j] == '1' && A[i] == N + 10) A[i] = dist1[j] + 1;
			if (j != start[i] && spec[j]) {
				B[i] = dist1[j];
				break;
			}
			for (signed k : adjlist[j]) {
				if (dist1[k] != N + 10) continue;
				if (S[k] == '0') {
					dist1[k] = dist1[j] + 1;
					bfs1.push_back(k);
				}
				else {
					dist1[k] = dist1[j];
					bfs1.push_front(k);
				}
			}
		}
		if (S[start[i]] == '1') A[i] = min(A[i], 2LL);
	}
	//for (int i : A) cout << i << ' ';
	//cout << '\n';
	//for (int i : B) cout << i << ' ';
	//cout << '\n';
	//for (int i = 0; i < N; i++) {
		//for (int j : dist[i]) cout << j << ' ';
		//cout << '\n';
	//}
	vector<int> funny, anss(N, INF);
	for (int i = 1; i < K; i++) funny.push_back(B[i] - A[i] + 2);
	sort(funny.begin(), funny.end());
	int crntcost = 0;
	vector<int> costs;
	for (int i = 0; i < N; i++) {
		costs.push_back(crntcost);
		//cout << crntcost << ' ' << i << '\n';
		//for (int j = 0; j < N; j++) anss[j] = min(anss[j], crntcost + dist[i][j]);
		if (i == 0) {
			for (int j : A) crntcost += j;
			continue;
		}
		crntcost += 2 * K - 2 - (int)(upper_bound(funny.begin(), funny.end(), i) - funny.begin());
	}
	vector<queue<signed>> funnyg(N, queue<signed>());
	funnyg[0].push(start[0]);
	vector<int> dist(N, INF);
	int crntoffset = 0;
	for (signed i = 0; i < N; i++) {
		for (signed j = 0; j < N; j++) {
			while (funnyg[j].size()) {
				signed k = funnyg[j].front(); funnyg[j].pop();
				if (dist[k] != INF) continue;
				dist[k] = crntoffset + j;
				if ((k != start[0] || j) && S[k] == '1') continue;
				for (signed l : adjlist[k]) if (j + 1 < N) funnyg[j + 1].push(l);
			}
		}
		for (signed j = 0; j < N; j++) anss[j] = min(anss[j], costs[i] + dist[j]);
		crntoffset = INF;
		for (signed j = 0; j < N; j++) if (S[j] == '1') crntoffset = min(crntoffset, dist[j] + 1);
		for (signed j = 0; j < N; j++) {
			if (S[j] == '0') continue;
			for (signed k : adjlist[j]) if (dist[j] + 1 - crntoffset < N) funnyg[dist[j] + 1 - crntoffset].push(k);
		}
		fill(dist.begin(), dist.end(), INF);
	}
	for (int i : anss) cout << i << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:92:51: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&, long long int)'
   92 |                 if (S[start[i]] == '1') A[i] = min(A[i], 2LL);
      |                                                ~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from Main.cpp:2:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
Main.cpp:92:51: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   92 |                 if (S[start[i]] == '1') A[i] = min(A[i], 2LL);
      |                                                ~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
Main.cpp:92:51: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   92 |                 if (S[start[i]] == '1') A[i] = min(A[i], 2LL);
      |                                                ~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5775 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note:   template argument deduction/substitution failed:
Main.cpp:92:51: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   92 |                 if (S[start[i]] == '1') A[i] = min(A[i], 2LL);
      |                                                ~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5785 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note:   template argument deduction/substitution failed:
Main.cpp:92:51: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   92 |                 if (S[start[i]] == '1') A[i] = min(A[i], 2LL);
      |                                                ~~~^~~~~~~~~~~