fork(1) download
copy 
  1. // @adi28galaxyak
  2. // Content: TAXI modified version
  3.  
  4. #include "bits/stdc++.h"
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef vector<int> VI;
  9. typedef vector< VI > VVI;
  10. typedef pair<int, int> pii;
  11. #define FF first
  12. #define SS second
  13. #define pb(v) push_back(v)
  14. #define mp(x,y) make_pair(x, y)
  15.  
  16. #define NITRO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17. #define s(n) scanf("%d",&n)
  18. #define rep(i,start,end) for(int i = start;i<end;i++)
  19.  
  20. const int MAX = 2000;
  21. const int inf = 1e9;
  22. int n, p, temp;
  23. VI taxi, passenger;
  24. vector< vector< pair<int, int> > > graph(MAX+5);
  25.  
  26. bool FindMatch(int i, const VVI &w, VI &mr, VI &mc, VI &seen) {
  27.   for (int j = 0; j < w[i].size(); j++) {
  28.     if (w[i][j] && !seen[j]) {
  29.       seen[j] = true;
  30.       if (mc[j] < 0 || FindMatch(mc[j], w, mr, mc, seen)) {
  31.         mr[i] = j;
  32.         mc[j] = i;
  33.         return true;
  34.       }
  35.     }
  36.   }
  37.   return false;
  38. }
  39.  
  40. int BipartiteMatching(const VVI &w, VI &mr, VI &mc) {
  41.   mr = VI(w.size(), -1);
  42.   mc = VI(w[0].size(), -1);
  43.  
  44.   int ct = 0;
  45.   for (int i = 0; i < w.size(); i++) {
  46.     VI seen(w[0].size());
  47.     if (FindMatch(i, w, mr, mc, seen)) ct++;
  48.   }
  49.   return ct;
  50. }
  51.  
  52. VI dij(int start){
  53.     VI dist(n+p+5, inf);
  54.     priority_queue<pii,vector<pii>, greater<pii> > q;
  55.  
  56.     dist[start] = 0;
  57.     q.push(pii(0, start));
  58.     int status = 0;
  59.     while(!q.empty()){
  60.         status++;
  61.         pii top = q.top();
  62.         q.pop();
  63.         int v = top.SS, cost = top.FF;
  64.         if(cost <= dist[v]){
  65.             for(int i=0; i<graph[v].size(); ++i){
  66.                 int v2 = graph[v][i].FF, d = graph[v][i].SS;
  67.                 if(dist[v2] > dist[v] + d){
  68.                     dist[v2] = dist[v] + d;
  69.                     q.push(pii(dist[v2], v2));
  70.                 }
  71.             }
  72.         }
  73.     }
  74.     return dist;
  75. }
  76.  
  77. void build(VI &disTh, VVI &distTaxi, VVI &v){
  78.     VI speed, ttime;
  79.     rep(i,0,n) s(temp), speed.pb(temp);
  80.     rep(i,0,n) s(temp), ttime.pb(temp);
  81.  
  82.     rep(i,0,n){
  83.         int capacity = speed[i]*ttime[i];
  84.         rep(j,0,p){
  85.             int totaldist = disTh[passenger[j]] + distTaxi[i][passenger[j]];
  86.             if(totaldist<=capacity) {
  87.                 v[i][j] = 1;
  88.             }
  89.         }
  90.     }
  91. }
  92.  
  93. int main(){
  94. 	if(false) {
  95. 		freopen("input01.txt","r",stdin);
  96. 		//freopen("output10.txt","w",stdout);
  97. 	}
  98. 	NITRO;
  99.  
  100. 	int tt, r, x, y, d;
  101. 	s(tt);
  102. 	while(tt--){
  103. 	    s(n);s(p);s(r);
  104.  
  105.         rep(i,0,MAX) graph[i].clear();
  106. 	    VVI v(505, VI(1005, 0));
  107. 	    VVI distTaxi(505);
  108. 	    taxi.clear();
  109. 	    passenger.clear();
  110. 	    rep(i,0,n) {
  111. 	        s(temp);
  112. 	        taxi.pb(temp);
  113.         }
  114.         rep(i,0,p){
  115.             s(temp);
  116.             passenger.pb(temp);
  117.         }
  118.  
  119. 	    rep(i,0,r){
  120. 	        s(x);s(y);s(d);
  121. 	        graph[x].pb(mp(y, d));
  122. 	        graph[y].pb(mp(x, d));
  123. 	    }
  124.  
  125.         VI distTh = dij(n+p+1); // from theatre
  126.  
  127.         rep(i,0,n){ // from each taxi
  128.             distTaxi[i] = dij(taxi[i]);
  129.         }
  130.         build(distTh, distTaxi, v);
  131.         VI left(505, -1), right(1005, -1);
  132.         printf("%d\n", BipartiteMatching(v,left,right));
  133.     }
  134. }
Time limit exceeded #stdin #stdout 5s 3880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Nqv5p2
language:
C++14 (gcc 8.3)
created:
8 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!