# Orange Boy Can You Solve It Out? Ep. 30 (Easy)

Solved!

Difficulty: Div2D-Div2E

If you prefer harder problem, please visit here

思考题 for dw

# Childish War (Easy)

Miss. Broken Tail(Wei Duan) is the Math teacher of NFLS Class 8 Junior 3.She is a kind teacher.

Miss. East(Fang Dong) is the Math teacher of NFLS Class 4 Junior 3.She is a kind teacher too.

Tail loves walking around the Xuanwu Lake to relax. So does East.

There are N islands numbered from 1 to N on Xuanwu Lake and there are M bidirectional weighted edges connecting them. It is made sure that the islands are connected and no edge has negative weight.

Tail is located at island S and East is located at island T. They decided to play a childish game.

The game has Q rounds, in each round Tail chooses an positive integer R1 and draw a circle centered at her position with the radius R1. East chooses an positive integer R2 and draw a circle centered at her position with the radius R2.

For each round, print how many islands are included in Tail's circle only and how many islands are included in East's circle only and how many islands are included in both circles.

# Example

**Input**

graph={

[1,2,2],

[2,3,2],

[1,4,2],

[4,3,2],

[1,3,3],

}

S=1 T=3

Query={

[2,1],

[4,4]

}

**Output**

3 0 1

0 4 0

**Explain**

Red for Tail, Blue For East, Green for All

# Constriants

Subtask1(50%):N,Q<=1000

Subtask2(50%):N,Q<=100000

# Solution

Provided by XGN:

First we need to find out the distance of each node to S and T -- d_S and d_T. A node can be seen as a point in 2d space.

Then we can perform 2D counting points using data structures (like segtree).

版权声明：

作者：XGN

链接：__https://blog.hellholestudios.top/archives/330__

来源：Hell Hole Studios Blog

文章版权归作者所有，未经允许请勿转载。

## 共有 1 条评论