제출 #409675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409675		victoriad	Football (info1cup20_football)	C++14	0 / 100	546 ms	1048580 KiB

football

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
int n,m;
vector<vector<pair<int,int> > >g;
vector<vector<int> >pos;

struct nodo{
	int dis,bu,po;
	nodo(int dis=0,int bu=0,int po=0):dis(dis),bu(bu),po(po){

	}
};

bool operator<(const nodo& d,const nodo& i){
	return d.dis<i.dis;
}

bool operator>(const nodo& d,const nodo& i){
	return d.dis>i.dis;
}


int solve(int raiz,vector<int>&b,vector<int>&p){
priority_queue<nodo,vector<nodo>, greater<nodo> >pq;
vector<vector<int> >dist(n);
vector<int>r(n,1e9);
for(int i=0;i<n;i++)dist[i]=r;
dist[b[0]][0]=0;
pq.push(nodo(dist[b[0]][0],0,0));

while(!pq.empty()){
	nodo no=pq.top();
	pq.pop();
	if(dist[no.bu][no.po]!=no.dis)continue;

	if(no.bu==b[1])return no.dis;

	if(no.po!=0){
		if(dist[no.bu][0]>no.dis){
			dist[no.bu][0]=no.dis;
			pq.push(nodo(dist[no.bu][0],no.bu,0));
		}

		if(no.bu+no.po<=n-1){
			if(dist[no.bu+no.po][no.po]>no.dis+1){
				dist[no.bu+no.po][no.po]=no.dis+1;
				pq.push(nodo(dist[no.bu+no.po][no.po],no.bu+no.po,no.po));
			}
		}

		if(no.bu-no.po>=0){
			if(dist[no.bu-no.po][no.po]>no.dis+1){
				dist[no.bu-no.po][no.po]=no.dis+1;
				pq.push(nodo(dist[no.bu-no.po][no.po],no.bu-no.po,no.po));
			}
		}
	}
	else{

		for(int i=0;i<g[no.bu].size();i++){
		if(dist[g[no.bu][i].first][0]>no.dis+g[no.bu][i].second){
			dist[g[no.bu][i].first][0]=no.dis+g[no.bu][i].second;
			pq.push(nodo(dist[g[no.bu][i].first][0],g[no.bu][i].first,0));
		}	
		}

		for(int i=0;i<pos[no.bu].size();i++){
			if(dist[no.bu][pos[no.bu][i]]>no.dis){
				dist[no.bu][pos[no.bu][i]]=no.dis;
				pq.push(nodo(dist[no.bu][pos[no.bu][i]],no.bu,pos[no.bu][i]));
			}
		}

	}
}
return -1;

}

void todascon(int power,int inicio){
int u=power+inicio,d=1;
while(u<=n-1){
	g[inicio].push_back(make_pair(u,d));
	u+=power;
	d++;
}
u=inicio-power;
d=1;
while(u>=0){
	g[inicio].push_back(make_pair(u,d));
	u-=power;
	d++;
}
}

int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
	cin>>n>>m;
	vector<int>b(m);
	vector<int>p(m);
	g.resize(n);
	pos.resize(n);

	for(int i=0;i<m;i++)cin>>b[i]>>p[i];
	
	int raiz=sqrt(n);
	for(int i=0;i<m;i++){
		if(p[i]>raiz){
			todascon(p[i],b[i]);
		}
		else{
			pos[b[i]].push_back(p[i]);
		}
	}

	cout<<solve(raiz,b,p);
	 
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

football.cpp: In function 'int solve(int, std::vector<int>&, std::vector<int>&)':
football.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i=0;i<g[no.bu].size();i++){
      |               ~^~~~~~~~~~~~~~~~
football.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=0;i<pos[no.bu].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 26
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 8
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8