제출 #132869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132869		DanerZein	Roller Coaster Railroad (IOI16_railroad)	C++14	11 / 100	1082 ms	169336 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define MAX 9000000000
using namespace std;
long long dp[100][100000];
long long dist[100][100];
long long l,tam;
long long tsp(long long id,long long mask){
  //cout<<id<<" "<<mask<<" "<<endl;
  printf("id: %d mask: %d\n",id,mask);
  if(mask==l)return 0;
  if(dp[id][mask]!=-1){
    return dp[id][mask];
  }
  long long r=MAX;
  for(int i=0;i<tam;i++){
    if((mask & (1<<i))==0){
      long long newmask=mask|(1<<i);
      r=min(r,tsp(i,newmask)+dist[i][id]);
      printf("i: %d newmask: %d r: %d\n",i,newmask,r);
    }
  }
  return dp[id][mask]=r;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  long long r;
  tam=t.size();
  if(tam<=8){
    vector<int>a,b;
    for(int i=0;i<tam;i++){
      a.push_back(i);
    }
    long long mi,d;
    mi=MAX;
    do{
      d=0;
      long long  v=1;
	bool sw=0;
	for(int i=0;i<a.size();i++){
	  if(i==0){
	    v=t[a[i]];
	  }
	  else{
	    int aux=v-s[a[i]];
	    if(aux>0){
	      d+=v-s[a[i]];
	    }
	    v=t[a[i]];
	  }
	}
	//	cout<<mi<<" "<<d<<endl<<" "<<sw;
	if(sw==0){
	  if(mi>d){
	  mi=min(mi,d);
	  b=a;
	  r=mi;
	  }
	}
       	/*for(int i=0;i<b.size();i++){
	  cout<<b[i]<<" ";
	}
	cout<<endl;*/
    }
    while(next_permutation(a.begin(),a.end()));
    }
  else{
  memset(dp,-1,sizeof dp);
  for(long long i=0;i<s.size();i++){
    for(long long j=i+1;j<s.size();j++){
      long long d=t[i]-s[j];
      if(d>=0){
	dist[i][j]=d;
      }
      else{
	dist[i][j]=0;
      }
      d=t[j]-s[i];
      if(d>=0){
	dist[j][i]=d;
      }
      else{
	dist[j][i]=0;
      }
    }
  }
  for(int i=0;i<s.size();i++){
    for(int j=0;j<s.size();j++){
      cout<<dist[i][j]<<" ";
    }
    cout<<endl;
  }
  cout<<endl;
  l=(1<<s.size())-1;
  long long r=tsp(0,1);
  for(int i=0;i<tam;i++){
    for(int j=0;j<l+1;j++){
      cout<<dp[i][j]<<" ";
    }
    cout<<endl;
  }
  }
  return r;
}

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

railroad.cpp: In function 'long long int tsp(long long int, long long int)':
railroad.cpp:10:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("id: %d mask: %d\n",id,mask);
                                     ^
railroad.cpp:10:37: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
railroad.cpp:20:53: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
       printf("i: %d newmask: %d r: %d\n",i,newmask,r);
                                                     ^
railroad.cpp:20:53: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
railroad.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(long long i=0;i<s.size();i++){
                     ~^~~~~~~~~
railroad.cpp:69:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long j=i+1;j<s.size();j++){
                         ~^~~~~~~~~
railroad.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
               ~^~~~~~~~~
railroad.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<s.size();j++){
                 ~^~~~~~~~~
railroad.cpp:94:13: warning: unused variable 'r' [-Wunused-variable]
   long long r=tsp(0,1);
             ^
railroad.cpp:102:10: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return r;
          ^

• Subtask 1: 11 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36