/* ID: nigo1 LANG: C++ TASK: checker */ #include #include #include #include #include #include #include #include #include #include #define inf 1ll << 61 using namespace std; // input: int N, M, F; int B[64], S[64], C[64], Cap[64]; //definition of i-th plane int dist[64][64]; //dist between two planets int People[64][64][4][17]; //people flying on [first_planet][second_planet][month][hour] flight int Cost[64][64][4][17]; //money that we will get on [first_planet][second_planet][month][hour] flight int Hour[64][64][4][17]; //hour of arrical on [first_planet][second_planet][month][hour] flight //------------ // users output: vector < pair > flight[64][4]; //cycle for every plane: flight[plane][day] = (starting_hour, destination_planet) bool can_fly[64][64]; // can_fly[p1][p2] = can we fly from p1 to p2? int cycle_len[64]; // the lenght of a cycle for every plane //------------ void scan_input() { scanf ("%d%d%d", &N, &M, &F); for (int i = 0; i < M; i++) { scanf ("%d%d%d%d", B + i, S + i, C + i, Cap + i), B[i]--; } memset (People, -1, sizeof People); for (int i = 0; i < F; i++) { int A, B, D, K, SH, EH, O, CT, P; scanf ("%d%d%d%d", &A, &B, &D, &K); A--, B--; can_fly[A][B] = 1; dist[A][B] = D; for (int month = 0; month < 4; month++) { for (int st_h = 4; st_h < 16; st_h++) { People[A][B][month][st_h] = 0; } } for (int j = 0; j < K; j++) { scanf ("%d%d%d%d%d", &SH, &EH, &O, &CT, &P); O--; Cost[A][B][O][SH] = CT; People[A][B][O][SH] = P; Hour[A][B][O][SH] = EH; } } } bool check(int); bool scan_flights() { int Y; int day, hour, planet; vector < pair > tmp; for (int i = 0; i < M; i++) { if (scanf("%d", &Y) != 1) { printf ("Less than M spaceships. "); return 0; } if (Y < 1) { printf ("Every cycle should have positive lenght. "); return 0; } if (Y > 50) { printf ("WTF?! Too much flights in the cycle. "); return 0; } tmp.clear(); for (int j = 0; j < Y; j++) { if (scanf ("%d%d%d", &day, &hour, &planet) != 3) { printf ("Not enough output data. "); return 0; } if (day <= 0 or day > 4) { printf ("Days of the cycle should be between 1 and 4. "); return 0; } if (hour < 4 or hour > 16) { printf ("Flights should start between 4 and 16 o'clock. "); return 0; } if (planet <= 0 or planet > N) { printf ("Planets in the cycle should be between 1 and N. "); return 0; } day--; planet--; flight[i][day].push_back ( make_pair (hour, planet) ); tmp.push_back ( make_pair (day, hour) ); } for (int j = 0; j < (int)tmp.size() - 1; j++) { if (tmp[j] >= tmp[j + 1]) { printf ("Flights are not sorted. "); return 0; // check if the times are correct } } if ( !check(i) ) { return 0; // check if the cycle is possible } } return 1; } bool used[64][64][4][64][17]; // used[planet1][planet2][month][day][hour] long long make_moves(int x) { long long res = 0; int base = B[x]; int speed = S[x]; int cost = C[x]; int capacity = Cap[x]; int len = cycle_len[x]; int current_day = 0; int current_planet = base; if (len == 0) return inf; for (int month = 0; month < 4; month++) for (int day = 0; day < 64; day++) { if (current_day == len) { //it is relax time :D current_day = 0; continue; } for (int j = 0; j < flight[x][current_day].size(); j++) { int destination_planet = flight[x][current_day][j].second; int start_hour = flight[x][current_day][j].first; int time_to_travel = (dist[current_planet][destination_planet] + speed - 1)/speed; //time to travel from current_planet to destination_planet int end_hour = start_hour + time_to_travel; //hour of arrival long long cost_to_travel = (long long)dist[current_planet][destination_planet]*cost; //cost for the flight if ( People[current_planet][destination_planet][month][start_hour] != 0 ) { //if there are expected flights if ( Hour[current_planet][destination_planet][month][start_hour] >= end_hour ) {//if the time of arrival is ok cost_to_travel -= (long long)Cost[current_planet][destination_planet][month][start_hour]*min(People[current_planet][destination_planet][month][start_hour], capacity); } } if ( used[current_planet][destination_planet][month][day][start_hour] ) { printf ("Two spaceships should not fly from one planet to another in the same time and direction. "); return inf; //two planes at the same time ... not good } used[current_planet][destination_planet][month][day][start_hour] = 1; current_planet = destination_planet; //go to the next planet res -= cost_to_travel; } current_day++; } return res; } bool check(int x) { int base = B[x]; int speed = S[x]; int cost = C[x]; int capacity = Cap[x]; int current_planet = base; int current_hour; int last_day = -1; for (int day = 0; day < 4; day++) { current_hour = 0; //for every day of the cycle start from hour 0 for (int j = 0; j < flight[x][day].size(); j++) { int destination_planet = flight[x][day][j].second; //get destination int start_hour = flight[x][day][j].first; //get starting hour if (start_hour < 4) { printf ("You can't fly during the everyday maintenance. "); return 0; //if starting hours is during the maintance ... not good } if (start_hour < current_hour) { printf ("Trying to take a flight while the spaceship is still flying. "); return 0; //if start_hour of the flight is before the last's flight arrival time ... not good } if ( !can_fly[current_planet][destination_planet] ) { printf ("No flights are allowed between the planets you are trying to fly. "); return 0; //if we can't fly from our current planet to the next one in the cycle ... break again } int time_to_travel = (dist[current_planet][destination_planet] + speed - 1)/speed; //time for completing the whole flight int end_hour = start_hour + time_to_travel; //arrival hour if (end_hour > 16) { printf ("Every spaceship should land before the end of the day. "); return 0; //is arrival hour after midnight } current_hour = end_hour; //update current hour current_planet = destination_planet; //update current planet } if ( !flight[x][day].empty() ) last_day = day; } if (current_planet != base) { printf ("A spaceship didn't manage to get back to the base for maintenance. "); return 0; //if the last planet we land on is diferent from the base ... assert } cycle_len[x] = last_day + 1; //store cycle_len for later return 1; //everything is ok } int main() { freopen ("flights.in", "r", stdin); //freopen ("checker.out", "w", stdout); scan_input(); freopen ("flights.out", "r", stdin); if (!scan_flights()) { printf ("Wrong answer!"); } else { long long ans = 0; for (int i = 0; i < M; i++) { long long tmp = make_moves(i); if (tmp == inf) { printf ("Wrong answer!"); return 0; } ans += tmp; } printf("OK: %lld\n", ans); } return 0; }