Submission #248906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
248906	2020-07-13T17:28:48 Z	pit4h	Soccer (JOI17_soccer)	C++14	Compilation error	0 ms	0 KB

soccer

#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>

#define st first
#define nd second
using ll = long long;
using namespace std;

const int H=502, N=1e5+2;
const ll INF = 1e16+1;
int h, w, n, s[N], t[N];
ll a, b, c;
bool player[N][N];

ll closest[H][H];
ll minX[H][H], maxX[H][H];

bool vis[H][H];
ll dist[H][H];
struct Obj {
	ll d;
	int x, y;
	
	bool operator<(Obj o) const{
		return d < o.d;	
	}
};

vector<int> moveX = {0, 0, 1, -1}, moveY = {1, -1, 0, 0};

bool inside(int x, int y) {
	if(x>=1 && x<=h && y>=1 && y<=w) return true;
	return false;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>h>>w;
	cin>>a>>b>>c;
	cin>>n;

	for(int i=0; i<n; ++i) { 
		cin>>s[i]>>t[i];	
		player[s[i]][t[i]] = 1;
	}
	
	for(int i=1; i<=w; ++i) {
		for(int x=1; x<=h; ++x) {
			for(int y=1; y<=w; ++y) {
				if(player[x][y]) maxX[x][y] = x;
				else maxX[x][y] = maxX[x-1][y];
			}
		}
	}
	for(int i=1; i<=w; ++i) {
		minX[h+1][i] = INF;
	}
	for(int x=1; x<=h; ++x) {
		for(int y=1; y<=w; ++y) {
			if(player[x][y]) minX[x][y] = x;
			else minX[x][y] = minX[x+1][y];
		}
	}

	for(int x=1; x<=h; ++x) {
		for(int y=1; y<=w; ++y) {
			closest[x][y] = INF;
			for(int i=1; i<=w; ++i) {
				closest[x][y] = min(closest[x][y], abs(y-i) + min( x - maxX[x][i], minX[x][i] - x));
			}
		}
	}

	for(int i=1; i<=h; ++i) {
		for(int j=1; j<=w; ++j) {
			dist[i][j] = INF;
		}
	}
	
	priority_queue< Obj > Q;
	Q.push({0, s[0], t[0]});
	dist[s[0]][t[0]] = 0;

	while(Q.size()) {
		auto cur = Q.top();
		Q.pop();
		ll d = cur.d;
		int x = cur.x;
		int y = cur.y;
		if(vis[x][y]) continue;
		vis[x][y] = 1;
		
		// C
		for(int i=0; i<4; ++i) {
			int nx = x+moveX[i], ny = y+moveY[i];
			if(inside(nx, ny) && d + c < dist[nx][ny]) {
				dist[nx][ny] = d + c;
				Q.push({d+c, nx, ny});
			}
		}

		//Ax + B
		for(int i=0; i<4; ++i) {
			for(int p=1; p<=max(h, w); ++p) {
				int nx = x+p*moveX[i], ny = y+p+moveY[i];
				ll nd = d + a*p + b + c * closest[nx][ny];
				if(inside(nx, ny) && nd < dist[nx][ny]) {
					dist[nx][ny] = nd;
					Q.push({nd, nx, ny});
				}
			}
		}
			
	}
	

}

Compilation message

/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<wchar_t>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIwEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<char>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIcEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa1): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x24f): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa9): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x114): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x294): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status