11167 - Monkeys in the Emei Mountain

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Tue Feb 20, 2007 1:26 am

Almost same challenge case:
5 2
1 0 1
2 2 4
2 2 4
1 0 2
2 0 4
0

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Feb 20, 2007 1:37 am

Ah yes, thanks! I should have seen that.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: 11167 Monkeys in the Emei Mountain

Post by rio » Tue Feb 20, 2007 6:12 am

krijger wrote:I got this problem accepted using a max-flow approach. But that algorithm barely runs in time (6,5 seconds) and for that I had to use a pretty efficient max-flow algorithm.

So I wonder if someone used another approach. Maybe some kind of dp or greedy, or backtracking with pruning, etc. I tried to think of these kind of techniques, but I don't see how they can be used.
I took the same approach as you and used Ford-Fulkerson algorithm for max-flow, but got runtime 0.391. Did you apply max-flow only for the intervals where > m monkeys ?

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Tue Feb 20, 2007 5:21 pm

I also use Ford-Fulkerson (with dijkstra / priority_queue to find the maximal augmenting path), but I did apply max-flow for all intervals (so not only for the intervals containing more than m monkeys).

But even after implementing this optimalization, it still runs for 6.322 secs. Can you send me your implementation / can I send you my implementation?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Feb 20, 2007 6:17 pm

Ofcourse :)
I'll send my code with PM. Also you can send me your code.

Noldorin
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm

Post by Noldorin » Tue Feb 20, 2007 11:33 pm

Hey, could you help me out with this problems, keeps giving me WA, not that i'm not used to, but i'm unable to find the flaw in the code.
I know that is really bad looking, i hope the error it's more obvious to you than has been for me.
Thanks!

Code: Select all

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <utility>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
#define sz(v) ((int)(v).size())
#define pb push_back
#define FORSZ(i,a,v) FOR(i,a,sz(v))
#define REPSZ(i,v) FORSZ(i,0,v)

inline int maxflow(VVI &matrix, int src, int dest){
	int cap[sz(matrix)];
	int in[sz(matrix)];
	int previous[sz(matrix)];
	int total = 0;
	while(true){
		int last = dest;
		memset(cap, 0, sizeof(cap));
		memset(in, 0, sizeof(in));
		queue<int> Q;
		Q.push(src);
		cap[src] = 999999;
		int done = 0, node;
		while(sz(Q) > 0){
			node = Q.front();
			Q.pop();
			if(node == dest){ done = 1; break;}
			else{
				FOR(i, 0, sz(matrix[node])){
					int obj = matrix[node][i];
					if(cap[i] < min(cap[node], obj)){
						cap[i] = min(cap[node], obj);
						previous[i] = node;
						if(in[i] == 0){
							Q.push(i);
							in[i] = 1;
							if(node == 1) break;
							//Only one at a time, if monkey A can't drink, we ahven't to test whit monkey A+1
						}
					}
				}
			}
		}
		if(done){
			total += cap[0];
			while(last != src){
				matrix[last][previous[last]] += cap[0];
				matrix[previous[last]][last] -= cap[0];
				last = previous[last];
			}
		}else break;
	}
	return total;
}


int main(){
	int monkeys, fonts, cases = 1;
	while(cin >> monkeys){
		if(monkeys == 0) return 0;
		cin >> fonts;
		int need[monkeys];
		int start[monkeys];
		int end[monkeys];
		int total = 0, minim = 9999999, maxim = 0;
		FOR(i, 0 , monkeys){
			cin >> need[i] >> start[i] >> end[i];
			total += need[i];
			if(start[i] < minim) minim = start[i];
			if(maxim < end[i]) maxim = end[i];
		}
		
		//Only making sure it's water for them all
		if(total > (maxim - minim) * fonts){
			cout << "Case " << cases << ": No" <<endl;
			cases++;
			continue;
		}
		//Signaling where to break the interval
		vector<int> placesToBreak(2*monkeys);
		FOR(i,0,monkeys){
			placesToBreak[i] = start[i];
			placesToBreak[monkeys+i] = end[i];
		}
		sort(placesToBreak.begin(), placesToBreak.end());
		
		int intervalFirst[monkeys + 2 + sz(placesToBreak)];
		int intervalLast[monkeys + 2 + sz(placesToBreak)];
		int firstEmpty = monkeys + 2;
		intervalFirst[firstEmpty] = placesToBreak[0];
		FOR(i, 1, 2*monkeys){
			if( placesToBreak[i] != placesToBreak[i-1]){
				intervalLast[firstEmpty] = placesToBreak[i];
				firstEmpty++;
				intervalFirst[firstEmpty] = placesToBreak[i];
			}
		}
		//Breaks saved
		
		//Creating the matrix and placing capacities
		//From monkey to interval
		//From interval to water
		//From source to monkeys (their thirstyness?)
		VVI matrix(firstEmpty, VI(firstEmpty,0));
		FOR(i, 0, monkeys)
			FOR(j, monkeys+1, firstEmpty)
				if(start[i] <= intervalFirst[j] && end[i] > intervalFirst[j])
					matrix[i+2][j] = intervalLast[j] - intervalFirst[j];
		FOR(i,monkeys+2,firstEmpty) matrix[i][0] = (intervalLast[i]-intervalFirst[i])*fonts;
		FOR(i,0,monkeys) matrix[1][i+2] = need[i];
		
		//Calling the maxflow
		int bo = maxflow(matrix, 1, 0);
		
		if(bo != total) cout << "Case " << cases << ": No" <<endl;
		else{
			cout << "Case " << cases << ": Yes" << endl;
			VI toPrint;
			int firstToUse[sz(matrix)];
			
			FOR(j, monkeys+2, sz(matrix)){
				firstToUse[j] = intervalFirst[j];
			}
			FOR(i, 0, monkeys){
				toPrint.clear();
				FOR(j, monkeys+2, sz(matrix)){
					int aux = intervalLast[j] - intervalFirst[j];
					if(start[i] <= intervalFirst[j] && end[i] > intervalFirst[j] && matrix[i+2][j] < aux){
						int sobren = firstToUse[j] - intervalFirst[j] - matrix[i+2][j];
						if( sobren <= 0 ){
							//See if one interval follows the last
							if(toPrint.size() == 0 || toPrint[sz(toPrint)-1] != firstToUse[j]){
								toPrint.pb(firstToUse[j]);
								toPrint.pb(firstToUse[j] + (intervalLast[j]-intervalFirst[j]) - matrix[i+2][j]);
								firstToUse[j] = toPrint[sz(toPrint)-1];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}else{
								//Puting this interval with the last
								toPrint[sz(toPrint)-1] = firstToUse[j] + (intervalLast[j]-intervalFirst[j]) - matrix[i+2][j];
								firstToUse[j] = toPrint[sz(toPrint)-1];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}
						}
						else{
							
							if(sz(toPrint)==0 || toPrint[sz(toPrint)-1]!=intervalFirst[j]){
								toPrint.pb(intervalFirst[j]);
								toPrint.pb(intervalFirst[j] + sobren);
								toPrint.pb(firstToUse[j]);
								toPrint.pb(intervalLast[j]);
								firstToUse[j] = toPrint[sz(toPrint)-3];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}else{
								//Puting this interval with the last
								toPrint[sz(toPrint)-1] = intervalFirst[j] + sobren;
								toPrint.pb(firstToUse[j]);
								toPrint.pb(intervalLast[j]);
								firstToUse[j] = toPrint[sz(toPrint)-3];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}
						}
					}
				}
				cout << sz(toPrint)/2;
				FOR(a,0,sz(toPrint)){
					cout << " ("<<toPrint[a]<<","<<toPrint[a+1]<<")";
					a++;
				}cout<<endl;
			}
		}
		cases++;
	}
}
Fear is the mind killer.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 21, 2007 5:02 am

Heres a simple corrector program I used to verify my program.Ofcourse, it only verfies the "Yes" answers. If there is a invalid output, it simply asserts.

Code: Select all

/* Lazy Correct Program */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>

typedef struct {
   int v, a, b;
} Monkey;
#define MAX_MONKEY 128
static Monkey mon[MAX_MONKEY];

int main()
{
   FILE *in, *out;

   in = fopen("in", "r");
   out = fopen("out", "r");


   int N, M, i, j, caseno = 1;
   char buf[64];
   while (fscanf(in, "%d", &N) && N) {
      fscanf(in, "%d", &M);
      for (i = 0; i < N; ++i)
         fscanf(in, "%d %d %d", &mon[i].v, &mon[i].a, &mon[i].b);

      printf("Case %d:\n", caseno++);
      fflush(stdout);

      fgets(buf, sizeof(buf), out);
      if (buf[strlen(buf)-2] == 'o') {
         printf("You answered \"No\". I can't verify.\n");
      } else {
         int *count = (int*)calloc(sizeof(int), 1024);
         for (i = 0; i < N; ++i) {
            int k, v;
            fscanf(out, "%d", &k);
            v = 0;
            int tmp = mon[i].a - 1;
            while ( k-- ) {
               int a, b;
               fscanf(out, " (%d,%d)", &a, &b);
               assert(a < b);
               assert(mon[i].a <= a && b <= mon[i].b);
               assert(tmp < a);
               tmp = b;
               v += b-a;
               for (; a < b; ++a)
                  assert(++count[a] <= M);
            }
            assert(v == mon[i].v);
         }
         free( count );
         fgets(buf, sizeof(buf), out);
         printf("\"Yes\" is yes!!\n");
      }
   }
}

Noldorin
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm

Post by Noldorin » Wed Feb 21, 2007 2:53 pm

Thank you very much, I've corrected some output errors so my code passes your test for the long input posted before, but still WA. I think I will give it up.
Fear is the mind killer.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Feb 23, 2007 9:34 pm

My max-flow is also slow, because I use stl vector to represent the graph.
Noldorin wrote:Hey, could you help me out with this problems, keeps giving me WA, not that i'm not used to, but i'm unable to find the flaw in the code.
I know that is really bad looking, i hope the error it's more obvious to you than has been for me.
Thanks!
Did your code handle cases when a monkey doesn't need to drink (v=0)?

Check your max-flow. There is also a bug with the index somewhere when you construct the graph. Also, I think how you compute what interval to print is wrong.

Below is what I do to print:

Code: Select all

REP(j,I-1) B[j]=ix[j];
REP(i,n) {
	vector<pair<int,int> > sol;
	REP(j,I-1) {
	  int x = F[i][n+j];
	  if(!x) continue;
	  int start=B[j],end=start+x,len=ix[j+1]-ix[j];
	  B[j]=end;
	  if(end<=ix[j+1])
	    sol.push_back(make_pair(start,end));
	  else {
	    sol.push_back(make_pair(start,ix[j+1]));
	    sol.push_back(make_pair(ix[j],end-len)), B[j]-=len;
	  }
	  if(B[j]==ix[j+1]) B[j]=ix[j];
	}
	sort(sol.begin(),sol.end());
	vector<pair<int,int> > r;
	REP(j,size(sol)) {
	  if(size(r) && r.back().second==sol[j].first)
	    r.back().second = sol[j].second;
	  else r.push_back(sol[j]);
	}
	cout << r.size();
	REP(j,size(r))
	  cout << " ("<<r[j].first<<','<<r[j].second<<')';
	cout << endl;
}
I won't say anything else about my code or I'll be spoiling it.

Noldorin
New poster
Posts: 4
Joined: Tue Feb 20, 2007 11:25 pm

Post by Noldorin » Sat Feb 24, 2007 1:07 pm

Thank you very much, finally accepted.
I had already corrected the output, the code up here has severeal glitches about intervals like (a,b)(b,c) and saving the instant of time in the interval when a monkey can enter in, but the error left was this small error on building the graph, and the most annoying part is that this error doesn't breaks the code on the public tests or the large input/output posted before.
Fear is the mind killer.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11167 - Monkeys in the Emei Mountain

Post by Angeh » Wed Sep 22, 2010 6:41 pm

Hi,Experts ...
i used FordFolkerson-Edmond Krap maxFlow Algorithm ...
i'm getting continuously WA ... Why!!!!!
check every thing 100 of thimes .... :(( i'm going crazy ...:((
can somebody help me ...
or if solved by this Method PM his/her code ...
I, have got AC on Problem 11358 (The same Without Printing ... ) so i should have problem in Printing ... but What ~!!! :((


thnaks in advance ...

Code: Select all

/*start 5.30
*/
#include<iostream>
#include<algorithm>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
struct Monkey{
    int v,s,e;
    Monkey(){};
}in[110];
const int MAX=400;
int cap[MAX][MAX],fnet[MAX][MAX],mark[MAX],parent[MAX],adj[MAX],deg[MAX],MA=1,out[MAX],outC=0;
int used[50010];
int inter[210],monkeyC;
#define Mon(n) (n+2)
#define Int(n) (2+monkeyC+n)

#define NN MAX // the maximum number of vertices[0,n),[i][j] = i->j edge
int q[NN], qf, qb, prev[NN];// BFS – Q
int FordFulkerson(int s, int t , int n){
    memset( fnet, 0, sizeof( fnet ) );// init the flow network
    int flow = 0;
    while( true ){
        memset( prev, -1, sizeof( prev ) );// find an augmenting path
        qf = qb = 0;
        prev[q[qb++] = s] = -2; //Enqueue
        while( qb > qf && prev[t] == -1 )//BFS //Dequeue
            for( int u = q[qf++], v = 0; v < n; v++ )
                if( prev[v] == -1 && fnet[u][v] < cap[u][v] )
                    prev[q[qb++] = v] = u;
        if( prev[t] == -1 ) break;// see if we're done
        int bot = 0x7FFFFFFF;  
        for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) // get the bottleneck capacity
           bot = min(bot,cap[u][v]-fnet[u][v]);
        for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )// update the flow network
            fnet[u][v] += bot,fnet[v][u] -= bot;
        flow += bot;
    }
    return flow;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m,ca=1;
    while(scanf("%d",&n)>0  && n ){
        scanf("%d",&m);
        monkeyC=n;
        FOR(i,n)scanf("%d%d%d",&in[i].v,&in[i].s,&in[i].e );
        FOR(i,n) inter[2*i]=in[i].s ,inter[2*i+1]=in[i].e;
        sort(inter,inter+2*n);
        memset(cap,0,sizeof(cap) );
        int src=0;
        int sink=1;
        //make Graph;
        int Sum=0;
        FOR(i,n)    Sum+=in[i].v;
        FOR(i,n)    cap[src][Mon(i)]=in[i].v;
        FOR(i,n){//monkey
            FOR(j,2*n-1){//interval [ .. )
                if( in[i].s<=inter[j] && inter[j]<in[i].e ){
                    cap[ Mon(i) ][ Int(j) ]= inter[j+1]-inter[j];
        //            printf("[%d][%d] = %d %d %d\n",Mon(i) , Int(j) ,inter[j],inter[j+1], inter[j+1]-inter[j] );
                }
            }
        }
        memset(used,0,sizeof(used) );
        FOR(i,2*n-1)    cap[Int(i) ][sink]=(inter[i+1]-inter[i])*m;
        int res=FordFulkerson(src,sink,Int(2*n) );
        //printf("%d\n",res);
        if(res==Sum){
            printf("Case %d: Yes\n",ca++);
            FOR(i,n){
                //printf("moneyk %d : ",i);
                outC=0;
                FOR(j,2*n-1){
                    if( fnet[ Mon(i)][ Int(j) ]>0  ){
                        int s=inter[j];
                        while( used[s]>=m)s++;
                        FOR(t,fnet[ Mon(i)][Int(j)] ){
                            //printf(">>%d\n",s);
                            used[s]++;
                            out[outC++]=s++;
                            if(outC>1 && out[outC-1]==out[outC-2])outC-=2;
                            out[outC++]=s;
                        }
                        
                    }
                }                
                //FOR(i,outC)printf("%d ",out[i] );
                printf("%d",outC/2);
                FOR(i,outC)printf(" (%d,%d)",out[i],out[i+1] ),++i;
                putchar('\n');
            }
        }
        else 
            printf("Case %d: No\n",ca++);
    }
    return 0;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

cosmin79
New poster
Posts: 11
Joined: Fri Aug 09, 2013 7:25 pm

Re: 11167 - Monkeys in the Emei Mountain

Post by cosmin79 » Fri Sep 20, 2013 7:01 pm

Can anyone help me figure out why do I get WA?? It works on every test I try. Can anyone take a look at my output formatting? Maybe there's a mistake there I can't see... Thank you in advance!

Code: Select all

    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <algorithm>
    #include <cstring>
    #define NMAX 105
    #define HMAX 405
    #define LMAX 505
    #define INF 1000000000
    #define pb push_back
    #define mp make_pair
    #define vi vector <int>
    #define pii pair <int, int>
    #define x first
    #define y second
    using namespace std;
    int n, m, no, val[HMAX], F[LMAX][LMAX], C[LMAX][LMAX];
    int source, dest, dad[LMAX], flow, expected, Q[LMAX];
    vi G[LMAX], I;
    vector <pii> sol;
    pair <int, pii> info[NMAX];
    bitset <LMAX> vis;

    void add_edge(int from, int to, int cap)
    {
        G[from].pb(to); C[from][to] = cap;
        G[to].pb(from);
    }

    void read()
    {
        int i, j, x, y;
        for (i = 1; i <= n; i++)
        {
            scanf("%d%d%d", &info[i].x, &info[i].y.x, &info[i].y.y);
            expected += info[i].x;  info[i].y.y--;
            I.pb(info[i].y.x); I.pb(info[i].y.y);
        }
        sort(I.begin(), I.end());
        I.erase(unique(I.begin(), I.end()), I.end());
       
        source = 0; no = I.size();
        for (i = 0; i < no - 1; i++)
        {
            val[2 * i + 1] = 1;
            val[2 * i + 2] = I[i + 1] - I[i] - 1;
        }
        val[2 * no - 1] = 1;
       
        for (i = 1; i <= 2 * no; i++)
            add_edge(source, i, val[i] * m);
         
        dest = 2 * no + n + 1;
        for (i = 1; i <= n; i++)
        {
            x = lower_bound(I.begin(), I.end(), info[i].y.x) - I.begin();
            y = lower_bound(I.begin(), I.end(), info[i].y.y) - I.begin();
            info[i].y = mp(2 * x + 1, 2 * y + 1);
           
            for (j = x; j < y; j++)
            {
                add_edge(2 * j + 1, 2 * no + i, val[2 * j + 1]);
                add_edge(2 * j + 2, 2 * no + i, val[2 * j + 2]);
            }
            add_edge(2 * y + 1, 2 * no + i, val[2 * y + 1]);
           
            add_edge(2 * no + i, dest, info[i].x);
        }
    }

    int BF()
    {
        vis.reset();
        Q[Q[0] = 1] = source; vis[source] = 1;
        int i, j, node, x;
        for (i = 1; i <= Q[0]; i++)
        {
            node = Q[i];
            for (j = 0; j < (int)G[node].size(); j++)
            {
                x = G[node][j];
                if (F[node][x] < C[node][x] && !vis[x])
                {
                    Q[++Q[0]] = x; dad[x] = node; vis[x] = 1;
                    if (x == dest)
                        return 1;
                }
            }
        }
       
        return vis[dest];
    }

    void max_flow()
    {
        int node, fmin;
        while (BF())
        {
            fmin = INF;
            for (node = dest; node != source; node = dad[node])
                fmin = min(fmin, C[dad[node]][node] - F[dad[node]][node]);
               
            for (node = dest; node != source; node = dad[node])
            {
                F[dad[node]][node] += fmin;
                F[node][dad[node]] -= fmin;
            }
           
            flow += fmin;
        }
    }

    void recons()
    {
        int i, j, x, y;
        for (i = 1; i <= n; i++)
        {
            for (j = info[i].y.x; j <= info[i].y.y; j++)
                if (F[j][i + 2 * no])
                {
                    x = I[(j - 1) / 2];  y = x + F[j][i + 2 * no];
                    if (!(j & 1))
                        x++, y++;
                       
                    if (sol.size() && sol[sol.size() - 1].y == x)
                        sol[sol.size() - 1].y = y;
                    else
                        sol.pb(mp(x, y));
                }
           
            printf("%d", sol.size());
            for (j = 0; j < (int)sol.size(); j++)
                printf(" (%d,%d)", sol[j].x, sol[j].y);
            printf("\n");
            sol.clear();
        }
    }

    void clear_data()
    {
        I.clear();
        int i;
        for (i = source; i <= dest; i++)
            G[i].clear();
        memset(F, 0, sizeof(F));
        memset(C, 0, sizeof(C));
        expected = flow = 0;
        memset(val, 0, sizeof(val));
    }

    int main()
    {
        //freopen("input", "r", stdin);
        int test_no = 0;
        while (scanf("%d%d", &n, &m), n)
        {
            test_no++;
           
            read();
            max_flow();
            printf("Case %d: ", test_no);
            if (flow == expected)
            {
                printf("Yes\n");
                recons();
            }
            else
                printf("No\n");
           
            clear_data();
        }
        return 0;
    }
Last edited by cosmin79 on Wed Sep 25, 2013 3:25 am, edited 1 time in total.

7maAqB
New poster
Posts: 1
Joined: Thu Oct 17, 2013 7:03 am

Re: 11167 - Monkeys in the Emei Mountain

Post by 7maAqB » Thu Oct 17, 2013 7:14 am

It's .rar file that include test generator, test checker by rio and one test

4shared link -> http://goo.gl/5mHu1H
gogoshare link -> http://goo.gl/xY9m0D

thank rio.

mike21
New poster
Posts: 5
Joined: Sat Jun 15, 2013 3:25 am

Re: 11167 - Monkeys in the Emei Mountain

Post by mike21 » Sun Oct 27, 2013 8:22 pm

How exactly can the intervals be contracted to 200 ?

flashion
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

Re: 11167 - Monkeys in the Emei Mountain

Post by flashion » Thu Aug 21, 2014 3:54 pm

Hello guys,

My approach to this problem is:
- created bipartite graph (monkeys, time from 0 to 50000)
- link monkeys to time vertexes, when they can drink (capacity 1)
- link source to monkeys (capacity: thirstyness of monkey)
- link time vertexes to sink (capacity: m)
- run maxflow with Dinic

and I got TLE which I expected, but I have no idea how to make it in another way.

Any help would be appreciated.

// EDIT: I "compressed" time intervals to O(n), but I'm getting WA :/

Post Reply

Return to “Volume 111 (11100-11199)”