JOI '14 - Factories

View as PDF

Points: 30 (partial)
Time limit: 2.75s
Memory limit: 512M

Problem types
Allowed languages
C, C++
Contest Day 1 - JOI Open Contest

In IOI Kingdom, there are cities numbered from to . These cities are connected by roads through which you can pass in both directions. You can travel from any city to any other city by passing through some of these roads.

In IOI Kingdom, there are many companies producing special components. Each company produces only one kind of components. No two companies produce the same kind of components. Each company has at least one factory. Each factory is built in one of the cities. More than one company may have factories in the same city.

Sometimes, a company requires components of another company. Assume the company requires the components of the company . In this case, they need to transport components from to . They may transport components from any of the factories of the company to any of the factories of the company . They need to choose factories appropriately to minimize the distance between factories.

First, the number of cities and the information of roads in IOI Kingdom are given. Then, queries are given. Each query is written in the following form: the company having factories in cities requires components of the company having factories in cities . Write a program which, for each query, returns the minimum distance to transport the components.

Implementation Details

You are to write a program which implements procedures to answer queries.
Your program should include the header file factories.h by #include "factories.h"
Your program should implement the following procedures.

void Init(int N, int A[], int B[], int D[])

• This procedure is called only once in the beginning. The parameter is the number of cities in IOI Kingdom. The parameters , and are arrays of length . The elements , and are three integers , and respectively. This means, for each , there is a road of length connecting the city and the city .
long long Query(int S, int X[], int T, int Y[])

• This procedure is called for each of queries. In the query , the parameters and are two integers and respectively. These are the numbers of cities where the companies , have factories respectively. The parameter is an array of length . The company has factories in cities . The parameter is an array of length . The company has factories in cities .
This procedure should return the minimum distance to transport components from the company to the company .

Constraints

All input data satisfy the following conditions.

• .
• .
• .
• .
• .
• .
• You can travel from any city to any other city through some of these roads.
• .
• .
• .
• .
• are different from each other .
• .
• .

The following conditions are satisfied.

• .
• .

The following conditions are satisfied.

• .
• .

Sample Input

7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5

Sample Output

12
3
11

Explanation

These are sample input and sample output of the sample grader.

• In query , the company has factories in the cities , , and the company has factories in the cities , . The distance from the factory of the company in the city to the factory of the company in the city is minimum. The minimum distance is .
• In the query , the company has factories in the cities , , , and the company has factories in the cites , . The distance from the factory of the company in the city to the factory of the company in the city is minimum. The minimum distance is .
• In the query , the company has factories in the city , and the company has factories in the city . The distance from the factory of the company in the city to the factory of the company in the city is minimum. The minimum distance is .

Since the official page does not seem to provide a grader, the following are made available for you to use.

factories.h

factories.cpp

The code in factories.h includes the prototype functions that you need to implement, but do not write your code in this file. The code in factories.cpp includes a sample of the functions you should fill in to solve the problem. You should submit the contents of this file to the judge to grading. The code in grader.cpp includes the main function and should be used to run judge your program.

If you are using g++, then you can compile the program with g++ factories.cpp grader.cpp -std=c++11. If you are using an IDE, then consult stack overflow on how to add files into your project.

• commented on May 25, 2020, 8:09 p.m.

I've submitted identical code to this problem several times. Sometimes I pass with a margin of 0.5s, and other times I TLE on the 3rd or even 2nd batch. Is this due to the judge inconsistencies pointed out in earlier comments, or might it be for a different reason, e.g. inconsistent behaviour in my code?

• commented on May 25, 2020, 9:34 p.m.

The judges mentioned earlier have long ceased to exist; I've hidden that comment to prevent future confusion.

The current judge images diverged a bit over the last week due to some ongoing testing, and I suspect your code (or GCC?) favored one configuration more than the other. After resetting the images, it doesn't look like your submission passes regardless of which judge it lands on -- it's really (< 50ms) close to the time limit on batches 2 and 3. These are your submissions running on two separate judges: 1, 2. (The third judge is currently reserved for testing only.)

I tried submitting some other submissions, but they weren't hit as hard as yours was. I'm not sure why that's the case, though.

• commented on July 29, 2019, 2:46 a.m. edited

I think subtask 2 contains cases with and . Can someone double check this?

Edit: Didn't see the "Report an issue" at first. I submitted a ticket as well now.

• commented on Jan. 5, 2020, 2:49 a.m.

Official test data suggests that and . I updated the subtask description.

• commented on May 13, 2019, 2:38 p.m.

The TL for this question on oj.uz is 8s. Shouldn't the TL for the problem here be raised especially considering that oj.uz is apparently much faster than DMOJ?

• commented on May 13, 2019, 2:40 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on May 13, 2019, 2:57 p.m. edited

Are we using the same judges as the original JOI 2014? No.

Either way, it doesn't mean limits can't be changed from their original.

• commented on May 13, 2019, 3:02 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.