ens-ulm-1

google hashcode 2014 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1/
Log | Files | Refs

lecture.cpp (5725B)


      1 #include <ctime>
      2 #include <vector>
      3 #include <map>
      4 #include <algorithm>
      5 #include <cstdio>
      6 #include <cstring>
      7 #include <cmath>
      8 
      9 const int N_SOMMETS_MAJ = 12000;
     10 const int N_ARETES_MAJ = 18000;
     11 const int N_DEGRE_MAJ = 6;
     12 
     13 using namespace std;
     14 
     15  int n_sommets;
     16  int n_aretes;
     17  int t_autorise;
     18  int n_vehicules;
     19  int s_depart;
     20 // 8255; //ulm
     21 double longitude_min, longitude_max;
     22 double latitude_min, latitude_max;
     23 double longitude[N_SOMMETS_MAJ];
     24 double latitude[N_SOMMETS_MAJ];
     25 
     26 // caracteristiques d'une arete
     27 int depart[N_ARETES_MAJ];//depart
     28 int arrivee[N_ARETES_MAJ];//arrivee
     29 bool dbsens[N_ARETES_MAJ];//rue a double sens
     30 int cout[N_ARETES_MAJ];//cout(temps)
     31 int longueur[N_ARETES_MAJ];//longueur
     32 
     33 vector<vector<int> > adj(N_SOMMETS_MAJ); // matrice d'adjacence
     34 
     35 map<pair<int, int>, int> id_arete;
     36 
     37 vector<int> _solution[8];
     38 
     39 void affiche_sortie(vector<int> trajectoires[], FILE *fp) {
     40   fprintf(fp, "%d\n", n_vehicules);
     41   for (int i=0; i< n_vehicules; i++) {
     42     fprintf(fp, "%d\n", (int) trajectoires[i].size());
     43     for (unsigned int j=0; j<trajectoires[i].size(); j++) {
     44       fprintf(fp, "%d\n", trajectoires[i][j]);
     45     }
     46   }
     47 }
     48 
     49 void affiche_sortie(vector<int> trajectoires[]) {
     50   affiche_sortie(trajectoires, stdout);
     51 }
     52 
     53 void affiche_sortie(vector<int> sol[], char *filename) {
     54   FILE *fp = fopen(filename, "w");
     55   affiche_sortie(sol, fp);
     56   fclose(fp);
     57 }
     58 
     59 // (temps_tronques)
     60 // format: score, temps1, temps2, ..., temps8
     61 // (ou vide si solution invalide)
     62 vector<int> evalue_solution(vector<int> trajectoires[]) {
     63   bitset<N_ARETES_MAJ> aretes;
     64   vector<int> resultat;
     65   resultat.push_back(0);
     66   
     67   int score = 0;
     68   for (int i=0; i< n_vehicules; i++) {
     69     int temps = 0;
     70     for (int j=0; j< int(trajectoires[i].size() - 1); j++) {
     71       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
     72       int a = id_arete[p];
     73       if (!a) {
     74 	fprintf(stderr,"ERREUR ! %d %d [%d -> %d]",i,j,trajectoires[i][j], trajectoires[i][j+1]);
     75         resultat.clear();
     76         return resultat;
     77       }
     78       temps += cout[a];
     79       if (temps >= t_autorise) {
     80         // undo
     81         temps -= cout[a];
     82         break;
     83       }
     84       if (!aretes[a]) {
     85         score += longueur[a];
     86         aretes[a] = 1;
     87       }
     88     }
     89     resultat.push_back(temps);
     90   }
     91   resultat[0] = score;
     92   return resultat;
     93 }
     94 
     95 int score_solution(vector<int> trajectoires[]) {
     96   vector<int> v = evalue_solution(trajectoires);
     97   return v[0];
     98 }
     99 
    100 // in-place truncation to a maximum
    101 // return 0 unless invalid edge
    102 int tronque_solution(vector<int> trajectoires[], int max_limit) {
    103   for (int i=0; i< n_vehicules; i++) {
    104     int temps = 0;
    105     for (int j=0; j< int(trajectoires[i].size() - 1); j++) {
    106       pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
    107       int a = id_arete[p];
    108       if (!a) {
    109         return -1;
    110       }
    111       temps += cout[a];
    112       if (temps > max_limit) {
    113         // j'ai deborde, je cesse la
    114         trajectoires[i].resize(j);
    115         break;
    116       }
    117     }
    118   }
    119   return 0;
    120 }
    121 int tronque_solution(vector<int> trajectoires[]) {
    122   return tronque_solution(trajectoires, t_autorise);
    123 }
    124 
    125 
    126 void lecture_entree(){
    127   scanf("%d",&n_sommets);
    128   scanf("%d",&n_aretes);
    129   scanf("%d",&t_autorise);
    130   scanf("%d",&n_vehicules);
    131   scanf("%d",&s_depart);
    132   for(int i=0;i<n_sommets;i++) {
    133     scanf("%lf %lf",&longitude[i],&latitude[i]);
    134   }
    135   longitude_min = *min_element(longitude, longitude + n_sommets);
    136   longitude_max = *max_element(longitude, longitude + n_sommets);
    137   latitude_min = *min_element(latitude, latitude + n_sommets);
    138   latitude_max = *max_element(latitude, latitude + n_sommets);
    139   for(int i=1;i<=n_aretes;i++){
    140     int x;
    141     scanf("%d %d %d %d %d",&depart[i],&arrivee[i],&x,&cout[i],&longueur[i]);
    142     dbsens[i]=(x==2);
    143     adj[depart[i]].push_back(arrivee[i]); 
    144     id_arete[make_pair(depart[i], arrivee[i])] = i;
    145     if(dbsens[i]) {
    146       adj[arrivee[i]].push_back(depart[i]);
    147       id_arete[make_pair(arrivee[i], depart[i])] = i;
    148     }
    149   }
    150 }
    151 
    152 int plus_proche(double x, double y) {
    153 
    154   int iBest = 0;
    155   double best = hypot(x - longitude[0], y - latitude[0]);
    156 
    157   for (int i = 1; i < n_sommets; i++) {
    158     double cur = hypot(x - longitude[i], y - latitude[i]);
    159     if (cur < best) {
    160       best = cur;
    161       iBest = i;
    162     }
    163   }
    164 
    165   return iBest;
    166 }
    167 
    168 int plus_proche_norm(double dx, double dy) {
    169 
    170   return plus_proche(longitude_min + dx * (longitude_max - longitude_min),
    171                      latitude_min + dy * (latitude_max - latitude_min));
    172 
    173 }
    174 
    175 void init_solution(vector<int> sol[]) {
    176 
    177   for (int i = 0; i < n_vehicules; i++)
    178     sol[i].push_back(s_depart);
    179 
    180 }
    181 void goto_etoile2(vector<int> sol[]) {
    182 
    183   for (int i = 0; i < n_vehicules; i++) {
    184     double x = .4 * (1+cos(2*i*M_PI/n_vehicules));
    185     double y = .4 * (1+sin(2*i*M_PI/n_vehicules));
    186     int p = plus_proche_norm(x, y);
    187     sol[i].push_back(p);
    188     fprintf(stderr, "Etoile2 %d: %lf, %lf -> %d (%lf, %lf)\n", i, x, y, p, longitude[p], latitude[p]);
    189   }
    190 
    191 }
    192 
    193 void goto_etoile(vector<int> sol[]) {
    194 
    195   for (int i = 0; i < n_vehicules; i++) {
    196     double x = .5 * (1+cos(2*i*M_PI/n_vehicules));
    197     double y = .5 * (1+sin(2*i*M_PI/n_vehicules));
    198     int p = plus_proche_norm(x, y);
    199     sol[i].push_back(p);
    200     fprintf(stderr, "Etoile %d: %lf, %lf -> %d (%lf, %lf)\n", i, x, y, p, longitude[p], latitude[p]);
    201   }
    202 
    203 }
    204 
    205 void lire_solution(const char *filename, vector<int> sol[]) {
    206   FILE *fp = fopen(filename, "r");
    207   if (!fp) {
    208     fprintf(stderr, "VĂ©rifie '%s'\n", filename);
    209     exit(1);
    210   }
    211   int n_veh;
    212   fscanf(fp, "%d", &n_veh);
    213   for (int v = 0; v < n_veh; v++) {
    214     int size;
    215     fscanf(fp, "%d", &size);
    216     for (int i = 0; i < size; i++) {
    217       int n;
    218       fscanf(fp, "%d", &n);
    219       sol[v].push_back(n);
    220     }
    221   }
    222   fclose(fp);
    223 }