1571 - Bus System

[ReynaldoGil]

http://coj.uci.cu/24h/problem.xhtml?abb=1571

I've seen many wrong answers to this problem, many of them in the test case 9, so it seems there's something weird here, so I ask for the admins to give at least an insight of what's wrong with that test case, or are the data tests wrong? I guess this problem wasn't taken from any other Olympiad, so it can't be found in Internet, please enlight us

[ReynaldoGil]

Anybody???
BTW who is dovier and what's the point on posting a link to every problem????

[dovier]

Hello ReynaldoGil,

BTW who is dovier (...)

1- I'm the current 'ACM-ICPC Caribbean Director' since 2009.
2- I'm a professor in the UCI since 2008.
3- I'm co-founder of the COJ and current member of the COJ Development Team (CDEVT).

(...) what's the point on posting a link to every problem????

1- Avoiding mess at the subforum 'Problem set' (several threads discussing the same problem).
2- Establishing a stronger link between the problem description and its corresponding discussion thread at the forum.
3- Among other issues ...

If you have more questions or suggestions about the system (COJ+Forum), please post it in the appropiate subforum.

Best regards,
Dovier.

[ReynaldoGil]

Oh, sorry, itś just I had a feeling of another spammer in the forum, then itś alright. The problem is that it was annoying to see a recent topic in the 24th page, so that nobody would be able to read it again... You should put all those posts pointing each problem to the back of the forum.
BTW can the administrators post the 9th test-case of the so called Bus System problem??
thank you, keep your great job

[dovier]

Hello ReynaldoGil,

The problem is that it was annoying to see a recent topic in the 24th page, so that nobody would be able to read it again...

You must use the option 'Mark forums read', so that hereinafter the freshest posts go up.

You should put all those posts pointing each problem to the back of the forum.

Believe me, I tried it ... but I didn't see any option to do that ... I recommend to use the search form or the sorting options listed at the end of the page.

thank you, keep your great job

You're welcome ... thank you to you for using our system!

Regards, Dovier.

[xshaka]

Hi ReynaldoGil:

I'm the creator of the Bus System problem, and even when the problem test data has been checked for some other judges before being posted, we may be wrong. Can you please comment your approach here?

Best regards.

[ReynaldoGil]

Well, sorry for answering so late, my approach is just to simulate it, bus by bus, using some STL structures to make it faster, it's a bit error prone, but I've checked it more than once. Any clue on where my mistake could be?

[ReynaldoGil]

Does anybody else have something to say, as far I imagine, there are no dark points in my approach, I can guess that the "public" approach is the same, so what's the explanation of the WA? I would post my code here, but I know it's forbiden

[xshaka]

Hi, my approach is similar I guess: I simulate the travel performed for every bus, but I think the key difference is I do need a more specific data structure for picking which group will get the bus at each stop. Could you please post your code? (it is allowed as long the code is not an AC code).

[ReynaldoGil]

ok, thank you, here you have it...

Code: Select all

#include <cstdio>
#include <list>
#include <set>
using namespace std;
const int MAX=100001;
struct group{
	int arrival, dest, size;
};
bool operator<(const group& a, const group& b)
{
	if(a.arrival!=b.arrival)return a.arrival<b.arrival;
	return a.size<b.size;
}
multiset<group> G[MAX];
list<group> stop[MAX];
int next[MAX]={0};
int T, N, M, Q;
int cap[MAX];
int time[MAX];
struct on{
	int num, dest;
};
bool operator<(const on& a, const on& b){
	return a.dest<b.dest;
}
int main() {
	int tem, totper=0;
	scanf("%d%d%d", &N, &T, &M);
	for(int i=1; i<=N; i++)scanf("%d", &cap[i]);
	time[1]=0;
	for(int i=1; i<M; i++)	{
		scanf("%d", &tem);
		time[i+1]=time[i]+tem;
	}
	scanf("%d", &Q);
	int A, B, C, D;
	for(int i=0; i<Q; i++)	{
		scanf("%d%d%d%d", &A, &B, &C, &D);
		G[C].insert((group){B, D, A});
		totper+=A;
	}
	int cur=0;
	for(int i=1; i<=M; i++)
		if(G[i].size()>0){
			stop[i].assign(G[i].begin(), G[i].end());
			next[cur]=i;
			cur=i;
		}

	cur=0;
	long long tottime=0;
	set<on>::iterator ss;
	list<group>::iterator it, ne;
	for(int i=1; i<=N && next[0]!=0; i++){
		multiset<on> bb;
		int p=0;
		int left=cap[i];
		while(next[p]!=0){
			cur=next[p];
			ss=bb.begin();
			while(ss!=bb.end()&& ss->dest <= cur)	{
				left+=ss->num;
				ss++;
			}
			bb.erase(bb.begin(), ss);
			it=stop[cur].begin();
			while(it!=stop[cur].end()){
				int curtime=(i-1)*T+time[cur];
				if(left>=it->size&&it->arrival<=curtime){
					tottime+=(long long)it->size*((i-1)*T+time[it->dest]-it->arrival);
					bb.insert((on){it->size, it->dest});
					left-=it->size;
					ne=it++;
					stop[cur].erase(ne);
				}
				else it++;
			}
			if(stop[cur].size()==0) next[p]=next[cur];
			else p=next[p];
		}
	}
	printf("%.3lf\n", (double)tottime/totper);
}

The struct on represent the people "on" the bus at every moment...