DMPG '15 G3 - Kinako Bread 2 - DMOJ: Modern Online Judge

DMPG '15 G3 - Kinako Bread 2

View as PDF

Submit solution

All submissions

Best submissions

Points: 30 (partial)

Time limit: 1.8s

Memory limit: 256M

Author:

FatalEagle

Problem types

Tohka's favorite food is kinako bread, but she likes croissants too. For dinner, Shido has bought Tohka some kinako bread and some croissants to eat, $N$ $N$ pieces in total, arranged on vertices of an undirected graph without cycles — a tree. The vertices in the tree are numbered from $1$ $1$ to $N$ $N$ . Tohka is very touched that Shido would buy her so much bread, but she is on a diet. For each of kinako bread and croissants, Tohka doesn't want to eat more than $R_k$ $R_{k}$ and $R_c$ $R_{c}$ loaves, respectively. However, the bread is so tasty that she would like to eat at least $L_k$ $L_{k}$ and $L_c$ $L_{c}$ loaves of it, respectively $(0 \le L_i \le R_i \le N)$ $(0 \leq L_{i} \leq R_{i} \leq N)$ . Tohka has decided that she will eat all the bread on the vertices in a path between two vertices of the tree, and no more. How many ways can she choose a path of the tree to eat?

Note: A path is a sequence of unique vertices such that each pair of adjacent vertices in the path are connected by an edge in the tree. Specifically, a sequence of one vertex is considered a path.

Input Specification

The first line of input will have $N$ $N$ , $L_k$ $L_{k}$ , $R_k$ $R_{k}$ , $L_c$ $L_{c}$ , $R_c$ $R_{c}$ .
The second line of input will have a string representing the type of bread on each vertex from $1$ $1$ to $N$ $N$ . The $i^\text{th}$ $i^{th}$ character will be K if the type of bread on vertex $i$ $i$ is kinako bread or C if it's a croissant.
The next $N-1$ $N - 1$ lines will contain the edges of the tree, in the format $u\ v$ $u v$ . That means there is an edge between vertex $u$ $u$ and vertex $v$ $v$ .

Constraints

Subtask 1 [30%]

$2 \le N \le 1\,000$ $2 \leq N \leq 1 000$

Subtask 2 [30%]

$2 \le N \le 200\,000$ $2 \leq N \leq 200 000$
$L_c = R_c = 0$ $L_{c} = R_{c} = 0$
All of the bread will be kinako bread.

Subtask 3 [40%]

$2 \le N \le 200\,000$ $2 \leq N \leq 200 000$

Output Specification

The output should consist of one integer on a single line, the number of ways Tohka can pick a path of the tree to eat.

Sample Input

Copy

Sample Output

Copy

Comments

13

verybadallen commented on April 11, 2020, 6:25 p.m. ← edit 4 →

const == SpontaneousCombustion copied the code of jeffreyxiao for this problem...

Original code: https://dmoj.ca/src/150170
Offender's code: https://dmoj.ca/src/2026383

Feel free to format the offender's code to compare them better. To the offender, please refrain from copying code in the future, whatever your reasons may be. This behaviour lacks integrity and honesty, especially when you simply steal the code of another and Ctrl-R some of the key variables effortlessly. We will continue to monitor your future submissions.

Edit: The offender did not even rename variables, just removed formatting... If you believe this is a false accusation, feel free to reply and we can discuss this over Discord.

Edit 2: To respond to both replies, we know const is SpontaneousCombustion because they access DMOJ from the same IP address. Also, they submit at the exact same time, if you want to look at it from a practical standpoint. const is unlisted from excessive amounts of code copying, so his rank does not show.

Edit 3: On a side note, PeterWang, next time you copy code try to make sure it's at least in English... https://dmoj.ca/src/2024331

6

2fecta commented on April 12, 2020, 5:03 a.m.

Problem:https://dmoj.ca/problem/apio10p1 Original:https://dmoj.ca/src/1966198 Copied:https://dmoj.ca/src/1977623
Problem:https://dmoj.ca/problem/coci14c7p5 Original:https://dmoj.ca/src/1564485 Copied:https://dmoj.ca/src/1944895
Problem:https://dmoj.ca/problem/ccc19s4 Original:https://dmoj.ca/src/1830996 Copied:https://dmoj.ca/src/1843794
To be fair it could just be similar code

Everyone copying bruce lol
Problem: https://dmoj.ca/problem/joi14p1 Original: https://dmoj.ca/src/2026536 Copied: https://dmoj.ca/src/2026536 Copied: https://dmoj.ca/src/2026565 Copied: https://dmoj.ca/src/2026528

-1

sjay05 commented on April 12, 2020, 10:09 p.m. ← edited →

how do you really know the difference between copied and similar. for some problems almost everyones code looks same

3

Plasmatic commented on April 12, 2020, 10:32 p.m.

it's easier for more complex problems

5

richardzhang commented on April 13, 2020, 3:38 a.m.

It's also obvious if you suddenly start submitting to problems which are well beyond your skill level...

Hmmmm... Looks familiar...

-3

Dan13llljws commented on April 12, 2020, 7:57 p.m.

it might be just that bruce is testing for them

-12

magicalsoup commented on April 11, 2020, 8:25 p.m. ← edited →

I checked their IP, and they have different IP.

Edit: I also checked their recent submissions, and I don't see any correlation between their submission times.

This comment is hidden due to too much negative feedback. Show it anyway.

5

verybadallen commented on April 11, 2020, 8:35 p.m. ← edit 2 →

Do you not realize there are services known as VPNs that change your public IP? Anyways, check your Discord for proof. Also, if you just check all const recent submissions, you will see that most of them coincide exactly with SpontaneousCombustion submission times. If that's not enough evidence, I don't know what is.

Edit: Literally all 5 of const solved problems are submitted at the same time as SpontaneousCombustion. Please actually check before you make false claims.

-6

sushi commented on April 11, 2020, 7:54 p.m.

how do you know that const == SpontaneousCombustion

This comment is hidden due to too much negative feedback. Show it anyway.

2

thealt commented on April 11, 2020, 7:47 p.m.

Why does const not have rank by points on his profile?

5

Plasmatic commented on April 11, 2020, 8:22 p.m.

It happens when you're unlisted from the points leaderboard, usually because you copied others' code for points.

10

discoverMe commented on June 11, 2019, 6:57 p.m.

my warning is so long that the judge won't run the program :(