Submission #537207

#	Time	Username	Problem	Language	Result	Execution time	Memory
537207		Gurban	Gap (APIO16_gap)	C++17	Compilation error	0 ms	0 KiB

gap

#include "bits/stdc++.h"
using namespace std;

using ll = long long;

const int maxn=3e4+5;
const int B = 180;
int n,m;
int b[maxn],p[maxn];
int ver[maxn][B];
int dis[maxn * B];
bool vis[maxn * B];
vector<pair<int,int>>E[maxn * B];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	int sq = sqrt(n) + 2;
	int sz = n - 1;
	for(int i = 0;i < n;i++) for(int j = 1;j <= sq;j++) ver[i][j] = ++sz;
	for(int i = 0;i < n;i++){
		for(int j = 1;j <= sq;j++){
			E[ver[i][j]].push_back({i,0});
			// E[i].push_back({ver[i][j],0});
			if(i - j >= 0) E[ver[i][j]].push_back({ver[i-j][j],1});
			if(i + j < n) E[ver[i][j]].push_back({ver[i+j][j],1});
		}
	}
	for(int i = 0;i < m;i++){
		cin >> b[i] >> p[i];
		if(p[i] <= sq){
			E[b[i]].push_back({ver[b[i]][p[i]],0});
			E[ver[b[i]][p[i]]].push_back({b[i],0});
		}
		else {
			for(int j = 1;b[i] - j * p[i] >= 0;j++) E[b[i]].push_back({b[i] - j * p[i],j});
			for(int j = 1;b[i] + j * p[i] < n;j++) E[b[i]].push_back({b[i] + j * p[i],j});
		}
	}

	// cout<<E[22][0].first<<' '<<E[22][0].second<<'\n';

	for(int i = 0;i <= sz;i++) dis[i] = 1e9;
	dis[b[0]] = 0;
	priority_queue<pair<int,int>>q;
	q.push({0,b[0]});
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		// cout<<x<<'\n';
		for(auto i : E[x]){
			if(dis[i.first] > dis[x] + i.second){
				dis[i.first] = dis[x] + i.second;
				q.push({-dis[i.first],i.first});
			}
		}
	}
	if(dis[b[1]] == 1e9) cout<<-1;
	else cout<<dis[b[1]];
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cctuF7BP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXw5mGP.o:gap.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cctuF7BP.o: in function `main':
grader.cpp:(.text.startup+0x1b7): undefined reference to `findGap(int, int)'
collect2: error: ld returned 1 exit status