daily pastebin goal
25%
SHARE
TWEET

Untitled

a guest Mar 13th, 2018 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     /*
  2.         Author       :  Jan
  3.         Problem Name :
  4.         Algorithm    :
  5.         Complexity   :
  6.     */
  7.      
  8.     #include <set>
  9.     #include <map>
  10.     #include <list>
  11.     #include <cmath>
  12.     #include <ctime>
  13.     #include <deque>
  14.     #include <queue>
  15.     #include <stack>
  16.     #include <cctype>
  17.     #include <cstdio>
  18.     #include <string>
  19.     #include <vector>
  20.     #include <cassert>
  21.     #include <cstdlib>
  22.     #include <cstring>
  23.     #include <sstream>
  24.     #include <iostream>
  25.     #include <algorithm>
  26.      
  27.     using namespace std;
  28.      
  29.     const int NN = 50;
  30.     const int MAX = 200;
  31.      
  32.     int deg[MAX], adj[MAX][MAX], cap[MAX][MAX], Cap[MAX][MAX], q[MAX];
  33.     int dinic( int n, int s, int t ) {
  34.         int prev[MAX], u, v, i, j, z, flow = 0, qh, qt, inc;
  35.         for( i = 0; i < n; i++ ) {
  36.             deg[i] = 0;
  37.             for( j = 0; j < n; j++ ) {
  38.                 Cap[i][j] = cap[i][j];
  39.                 if( cap[i][j] || cap[j][i] ) adj[i][ deg[i]++ ] = j;
  40.             }
  41.         }
  42.         while(1) {
  43.             memset( prev, -1, sizeof( prev ) );
  44.             qh = qt = 0;
  45.             prev[s] = -2;
  46.             q[qt++] = s;
  47.             while( qt != qh && prev[t] == -1 ) {
  48.                 u = q[qh++];
  49.                 for(i = 0; i < deg[u]; i++) {
  50.                     v = adj[u][i];
  51.                     if( prev[v] == -1 && cap[u][v] ) {
  52.                         prev[v] = u;
  53.                         q[qt++] = v;
  54.                     }
  55.                 }
  56.             }
  57.             if(prev[t] == -1) break;
  58.             for(z = 0; z < n; z++) if( prev[z] !=- 1 && cap[z][t] ) {
  59.                 inc = cap[z][t];
  60.                 for( v = z, u = prev[v]; u >= 0; v = u, u=prev[v]) inc = min( inc, cap[u][v] );
  61.                 if( !inc ) continue;
  62.                 cap[z][t] -= inc;
  63.                 cap[t][z] += inc;
  64.                 for(v=z, u = prev[v]; u >= 0; v = u, u = prev[v]) {
  65.                     cap[u][v] -= inc;
  66.                     cap[v][u] += inc;
  67.                 }
  68.                 flow += inc;
  69.             }
  70.         }
  71.         return flow;
  72.     }
  73.      
  74.     int denoteInfo( int k ) {
  75.         if( k <= 26 ) return k + 96;
  76.         return k - 26 + 64;
  77.     }
  78.      
  79.     char res[10005][30];
  80.      
  81.     int main() {
  82.         freopen("a1.in", "r", stdin);
  83.         freopen("a1.ans", "w", stdout);
  84.      
  85.         double cl = clock();
  86.      
  87.         int cases, caseno = 0;
  88.         scanf("%d", &cases);
  89.         while( cases-- ) {
  90.             int n, t, c, e, a[NN+5], d[NN+5], f[NN+5], I[2*NN+5][2], K = 0, needFlow = 0;
  91.             set <int> S;
  92.             scanf("%d %d %d %d", &n, &t, &c, &e);
  93.             assert(1 <= n && n <= 50 && 1 <= t && t <= 5 && 1 <= c && c <= 5 && 2 <= e && e <= 10000);
  94.             for( int i = 1; i <= n; i++ ) {
  95.                 scanf("%d %d %d", &a[i], &d[i], &f[i]);
  96.                 assert( 1 <= a[i] && a[i] < d[i] && 1 <= f[i] && f[i] <= d[i] - a[i] );
  97.                 S.insert( a[i] );
  98.                 S.insert( d[i] );
  99.             }
  100.             for( set <int>::iterator s = S.begin(), s1; s != S.end(); s++ ) {
  101.                 s1 = s;
  102.                 s1++;
  103.                 if( s1 == S.end() ) break;
  104.                 I[++K][0] = *s;
  105.                 I[K][1] = (*s1) - 1;
  106.             }
  107.             memset( cap, 0, sizeof(cap) );
  108.             for( int i = 1; i <= n; i++ ) {
  109.                 cap[0][i] = f[i];
  110.                 needFlow += f[i];
  111.                 for( int j = 1; j <= K; j++ ) if( a[i] <= I[j][0] && d[i] > I[j][1] ) cap[i][n+j] = I[j][1] - I[j][0] + 1;
  112.             }
  113.             for( int j = 1; j <= K; j++ ) cap[n+j][n+K+1] = ( I[j][1] - I[j][0] + 1 ) * t * c;
  114.             printf("Case %d: ", ++caseno);
  115.             if( needFlow != dinic( n+K+2, 0, n+K+1 ) ) {
  116.                 puts("No");
  117.                 continue;
  118.             }
  119.             puts("Yes");
  120.      
  121.             for( int i = 0; i < e - 1; i++ ) {
  122.                 for( int j = 0; j < t*c; j++ ) res[i][j] = '.';
  123.                 res[i][t*c] = 0;
  124.             }
  125.      
  126.             for( int j = 1; j <= K; j++ ) {
  127.                 priority_queue < pair <int, int> > Q, R;
  128.                 for( int i = 1; i <= n; i++ ) if( Cap[i][j+n] > cap[i][j+n] ) Q.push( make_pair( Cap[i][j+n] - cap[i][j+n], i ) );
  129.                 for( int k = I[j][0]; k <= I[j][1]; k++ ) R.push( make_pair( t*c, k ) );
  130.      
  131.                 while( !Q.empty() ) {
  132.                     pair <int, int> u = Q.top(); Q.pop();
  133.                     stack < pair <int, int> > temp;
  134.                     for( int y = 0; y < u.first; y++ ) {
  135.                         pair <int, int> v = R.top(); R.pop();
  136.                         res[v.second-1][--v.first] = denoteInfo( u.second );
  137.                         if( v.first ) temp.push( v );
  138.                     }
  139.                     while( !temp.empty() ) {
  140.                         R.push( temp.top() );
  141.                         temp.pop();
  142.                     }
  143.                 }
  144.             }
  145.             for( int i = 0; i < e - 1; i++ ) {
  146.                 for( int j = 0; j < t; j++ ) {
  147.                     for( int k = 0; k < c; k++ ) putchar( res[i][j*c+k] );
  148.                     if( j < t - 1 ) putchar('|');
  149.                 }
  150.                 puts("");
  151.             }
  152.         }
  153.      
  154.         cl = clock() - cl;
  155.         fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC);
  156.      
  157.         return 0;
  158.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top