Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author : Jan
- Problem Name :
- Algorithm :
- Complexity :
- */
- #include <set>
- #include <map>
- #include <list>
- #include <cmath>
- #include <ctime>
- #include <deque>
- #include <queue>
- #include <stack>
- #include <cctype>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <cassert>
- #include <cstdlib>
- #include <cstring>
- #include <sstream>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int NN = 50;
- const int MAX = 200;
- int deg[MAX], adj[MAX][MAX], cap[MAX][MAX], Cap[MAX][MAX], q[MAX];
- int dinic( int n, int s, int t ) {
- int prev[MAX], u, v, i, j, z, flow = 0, qh, qt, inc;
- for( i = 0; i < n; i++ ) {
- deg[i] = 0;
- for( j = 0; j < n; j++ ) {
- Cap[i][j] = cap[i][j];
- if( cap[i][j] || cap[j][i] ) adj[i][ deg[i]++ ] = j;
- }
- }
- while(1) {
- memset( prev, -1, sizeof( prev ) );
- qh = qt = 0;
- prev[s] = -2;
- q[qt++] = s;
- while( qt != qh && prev[t] == -1 ) {
- u = q[qh++];
- for(i = 0; i < deg[u]; i++) {
- v = adj[u][i];
- if( prev[v] == -1 && cap[u][v] ) {
- prev[v] = u;
- q[qt++] = v;
- }
- }
- }
- if(prev[t] == -1) break;
- for(z = 0; z < n; z++) if( prev[z] !=- 1 && cap[z][t] ) {
- inc = cap[z][t];
- for( v = z, u = prev[v]; u >= 0; v = u, u=prev[v]) inc = min( inc, cap[u][v] );
- if( !inc ) continue;
- cap[z][t] -= inc;
- cap[t][z] += inc;
- for(v=z, u = prev[v]; u >= 0; v = u, u = prev[v]) {
- cap[u][v] -= inc;
- cap[v][u] += inc;
- }
- flow += inc;
- }
- }
- return flow;
- }
- int denoteInfo( int k ) {
- if( k <= 26 ) return k + 96;
- return k - 26 + 64;
- }
- char res[10005][30];
- int main() {
- freopen("a1.in", "r", stdin);
- freopen("a1.ans", "w", stdout);
- double cl = clock();
- int cases, caseno = 0;
- scanf("%d", &cases);
- while( cases-- ) {
- int n, t, c, e, a[NN+5], d[NN+5], f[NN+5], I[2*NN+5][2], K = 0, needFlow = 0;
- set <int> S;
- scanf("%d %d %d %d", &n, &t, &c, &e);
- assert(1 <= n && n <= 50 && 1 <= t && t <= 5 && 1 <= c && c <= 5 && 2 <= e && e <= 10000);
- for( int i = 1; i <= n; i++ ) {
- scanf("%d %d %d", &a[i], &d[i], &f[i]);
- assert( 1 <= a[i] && a[i] < d[i] && 1 <= f[i] && f[i] <= d[i] - a[i] );
- S.insert( a[i] );
- S.insert( d[i] );
- }
- for( set <int>::iterator s = S.begin(), s1; s != S.end(); s++ ) {
- s1 = s;
- s1++;
- if( s1 == S.end() ) break;
- I[++K][0] = *s;
- I[K][1] = (*s1) - 1;
- }
- memset( cap, 0, sizeof(cap) );
- for( int i = 1; i <= n; i++ ) {
- cap[0][i] = f[i];
- needFlow += f[i];
- 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;
- }
- for( int j = 1; j <= K; j++ ) cap[n+j][n+K+1] = ( I[j][1] - I[j][0] + 1 ) * t * c;
- printf("Case %d: ", ++caseno);
- if( needFlow != dinic( n+K+2, 0, n+K+1 ) ) {
- puts("No");
- continue;
- }
- puts("Yes");
- for( int i = 0; i < e - 1; i++ ) {
- for( int j = 0; j < t*c; j++ ) res[i][j] = '.';
- res[i][t*c] = 0;
- }
- for( int j = 1; j <= K; j++ ) {
- priority_queue < pair <int, int> > Q, R;
- 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 ) );
- for( int k = I[j][0]; k <= I[j][1]; k++ ) R.push( make_pair( t*c, k ) );
- while( !Q.empty() ) {
- pair <int, int> u = Q.top(); Q.pop();
- stack < pair <int, int> > temp;
- for( int y = 0; y < u.first; y++ ) {
- pair <int, int> v = R.top(); R.pop();
- res[v.second-1][--v.first] = denoteInfo( u.second );
- if( v.first ) temp.push( v );
- }
- while( !temp.empty() ) {
- R.push( temp.top() );
- temp.pop();
- }
- }
- }
- for( int i = 0; i < e - 1; i++ ) {
- for( int j = 0; j < t; j++ ) {
- for( int k = 0; k < c; k++ ) putchar( res[i][j*c+k] );
- if( j < t - 1 ) putchar('|');
- }
- puts("");
- }
- }
- cl = clock() - cl;
- fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC);
- return 0;
- }
Add Comment
Please, Sign In to add comment