fork(2) download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <iostream>
  4. #include <queue>
  5. #include <set>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <vector>
  9. using namespace std;
  10.  
  11. struct street_info { int B, E, L, period_length, green_start, green_end; };
  12. struct event { int timestamp, car_id; };
  13. bool operator< (const event &A, const event &B) { if (A.timestamp != B.timestamp) return A.timestamp < B.timestamp; else return A.car_id < B.car_id; }
  14.  
  15. int D, I, S, V, F, A;
  16. unordered_map<string,int> street_id;
  17. vector<string> reverse_street_id;
  18. vector<street_info> streets;
  19. vector< vector<int> > car_paths;
  20. vector< queue<int> > traffic_lights;
  21.  
  22. int main() {
  23.     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  24.     cin >> D >> I >> S >> V >> F;
  25.  
  26.     for (int s=0; s<S; ++s) {
  27.         int b, e, l; string label;
  28.         cin >> b >> e >> label >> l;
  29.         street_id[label] = s;
  30.         streets.push_back( {b,e,l,1,0,0} );
  31.         reverse_street_id.push_back(label);
  32.     }
  33.  
  34.     traffic_lights.resize(S);
  35.  
  36.     for (int v=0; v<V; ++v) {
  37.         vector<int> path;
  38.         int P;
  39.         cin >> P;
  40.         string label;
  41.         while (P--) { cin >> label; path.push_back( street_id[label] ); }
  42.         car_paths.push_back(path);
  43.         traffic_lights[path[0]].push(v);
  44.     }
  45.  
  46.     cin >> A;
  47.     for (int a=0; a<A; ++a) {
  48.         int intersection;
  49.         cin >> intersection;
  50.         int E;
  51.         cin >> E;
  52.         vector<int> street_order;
  53.         vector<int> times;
  54.         int total_time = 0;
  55.         for (int e=0; e<E; ++e) {
  56.             string label; int t;
  57.             cin >> label >> t;
  58.             int str = street_id[label];
  59.             street_order.push_back(str);
  60.             times.push_back(t);
  61.             total_time += t;
  62.         }
  63.         int cur_time = 0;
  64.         for (int e=0; e<E; ++e) {
  65.             int str = street_order[e];
  66.             streets[str].period_length = total_time;
  67.             streets[str].green_start = cur_time;
  68.             cur_time += times[e];
  69.             streets[str].green_end = cur_time;
  70.         }
  71.     }
  72.  
  73.     set<event> future_events;
  74.     vector<int> car_path_segment(V, 0);
  75.  
  76.     set<int> streets_with_waiting_cars;
  77.     for (int s=0; s<S; ++s) if (!traffic_lights[s].empty()) streets_with_waiting_cars.insert(s);
  78.  
  79.     int SCORE = 0;
  80.  
  81.     for (int timestamp = 0; timestamp <= D; ++timestamp) {
  82.         while (!future_events.empty() && future_events.begin()->timestamp == timestamp) {
  83.             int car = future_events.begin()->car_id;
  84.             future_events.erase( future_events.begin() );
  85.             int cps = car_path_segment[car];
  86.             if (cps == int(car_paths[car].size())-1) SCORE += F + (D - timestamp); else {
  87.                 int str = car_paths[car][cps];
  88.                 traffic_lights[str].push(car);
  89.                 streets_with_waiting_cars.insert(str);
  90.             }
  91.         }
  92.  
  93.         vector<int> emptied_streets;
  94.         if (timestamp == D) break;
  95.         for (int s : streets_with_waiting_cars) {
  96.  
  97.             int ts = (streets[s].period_length == 0 ? -1 : timestamp % streets[s].period_length);
  98.             if (ts < streets[s].green_start || ts >= streets[s].green_end) continue;
  99.  
  100.             int car = traffic_lights[s].front();
  101.             traffic_lights[s].pop();
  102.             if (traffic_lights[s].empty()) emptied_streets.push_back(s);
  103.  
  104.             ++car_path_segment[car];
  105.             int str = car_paths[car][ car_path_segment[car] ];
  106.             future_events.insert( {timestamp + streets[str].L, car} );
  107.         }
  108.         for (int s : emptied_streets) streets_with_waiting_cars.erase(s);
  109.     }
  110.     cout << "SCORE: " << SCORE << endl;
  111. }
Success #stdin #stdout 0s 5020KB
comments (?)
stdin
copy 
6 4 5 2 1000
2 0 rue-de-londres 1
0 1 rue-d-amsterdam 1
3 1 rue-d-athenes 1
2 3 rue-de-rome 2
1 2 rue-de-moscou 3
4 rue-de-londres rue-d-amsterdam rue-de-moscou rue-de-rome
3 rue-d-athenes rue-de-moscou rue-de-londres
3
1
2
rue-d-athenes 2
rue-d-amsterdam 1
0
1
rue-de-londres 2
2
1
rue-de-moscou 1
stdout
copy 
SCORE: 1002
https://ideone.com/OeYtmy
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!